1// Copyright 2012 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/ast/ast.h"
6
7#include <cmath>  // For isfinite.
8
9#include "src/ast/prettyprinter.h"
10#include "src/ast/scopes.h"
11#include "src/base/hashmap.h"
12#include "src/builtins.h"
13#include "src/code-stubs.h"
14#include "src/contexts.h"
15#include "src/conversions.h"
16#include "src/parsing/parser.h"
17#include "src/property-details.h"
18#include "src/property.h"
19#include "src/string-stream.h"
20#include "src/type-info.h"
21
22namespace v8 {
23namespace internal {
24
25// ----------------------------------------------------------------------------
26// All the Accept member functions for each syntax tree node type.
27
28#define DECL_ACCEPT(type)                                       \
29  void type::Accept(AstVisitor* v) { v->Visit##type(this); }
30AST_NODE_LIST(DECL_ACCEPT)
31#undef DECL_ACCEPT
32
33
34// ----------------------------------------------------------------------------
35// Implementation of other node functionality.
36
37#ifdef DEBUG
38
39void AstNode::Print(Isolate* isolate) {
40  AstPrinter::PrintOut(isolate, this);
41}
42
43
44void AstNode::PrettyPrint(Isolate* isolate) {
45  PrettyPrinter::PrintOut(isolate, this);
46}
47
48#endif  // DEBUG
49
50
51bool Expression::IsSmiLiteral() const {
52  return IsLiteral() && AsLiteral()->value()->IsSmi();
53}
54
55
56bool Expression::IsStringLiteral() const {
57  return IsLiteral() && AsLiteral()->value()->IsString();
58}
59
60
61bool Expression::IsNullLiteral() const {
62  if (!IsLiteral()) return false;
63  Handle<Object> value = AsLiteral()->value();
64  return !value->IsSmi() &&
65         value->IsNull(HeapObject::cast(*value)->GetIsolate());
66}
67
68bool Expression::IsUndefinedLiteral() const {
69  if (IsLiteral()) {
70    Handle<Object> value = AsLiteral()->value();
71    if (!value->IsSmi() &&
72        value->IsUndefined(HeapObject::cast(*value)->GetIsolate())) {
73      return true;
74    }
75  }
76
77  const VariableProxy* var_proxy = AsVariableProxy();
78  if (var_proxy == NULL) return false;
79  Variable* var = var_proxy->var();
80  // The global identifier "undefined" is immutable. Everything
81  // else could be reassigned.
82  return var != NULL && var->IsUnallocatedOrGlobalSlot() &&
83         var_proxy->raw_name()->IsOneByteEqualTo("undefined");
84}
85
86
87bool Expression::IsValidReferenceExpressionOrThis() const {
88  return IsValidReferenceExpression() ||
89         (IsVariableProxy() && AsVariableProxy()->is_this());
90}
91
92
93VariableProxy::VariableProxy(Zone* zone, Variable* var, int start_position,
94                             int end_position)
95    : Expression(zone, start_position),
96      bit_field_(IsThisField::encode(var->is_this()) |
97                 IsAssignedField::encode(false) |
98                 IsResolvedField::encode(false)),
99      raw_name_(var->raw_name()),
100      end_position_(end_position) {
101  BindTo(var);
102}
103
104
105VariableProxy::VariableProxy(Zone* zone, const AstRawString* name,
106                             Variable::Kind variable_kind, int start_position,
107                             int end_position)
108    : Expression(zone, start_position),
109      bit_field_(IsThisField::encode(variable_kind == Variable::THIS) |
110                 IsAssignedField::encode(false) |
111                 IsResolvedField::encode(false)),
112      raw_name_(name),
113      end_position_(end_position) {}
114
115
116void VariableProxy::BindTo(Variable* var) {
117  DCHECK((is_this() && var->is_this()) || raw_name() == var->raw_name());
118  set_var(var);
119  set_is_resolved();
120  var->set_is_used();
121}
122
123
124void VariableProxy::AssignFeedbackVectorSlots(Isolate* isolate,
125                                              FeedbackVectorSpec* spec,
126                                              FeedbackVectorSlotCache* cache) {
127  if (UsesVariableFeedbackSlot()) {
128    // VariableProxies that point to the same Variable within a function can
129    // make their loads from the same IC slot.
130    if (var()->IsUnallocated() || var()->mode() == DYNAMIC_GLOBAL) {
131      ZoneHashMap::Entry* entry = cache->Get(var());
132      if (entry != NULL) {
133        variable_feedback_slot_ = FeedbackVectorSlot(
134            static_cast<int>(reinterpret_cast<intptr_t>(entry->value)));
135        return;
136      }
137      variable_feedback_slot_ = spec->AddLoadGlobalICSlot(var()->name());
138      cache->Put(var(), variable_feedback_slot_);
139    } else {
140      variable_feedback_slot_ = spec->AddLoadICSlot();
141    }
142  }
143}
144
145
146static void AssignVectorSlots(Expression* expr, FeedbackVectorSpec* spec,
147                              FeedbackVectorSlot* out_slot) {
148  Property* property = expr->AsProperty();
149  LhsKind assign_type = Property::GetAssignType(property);
150  if ((assign_type == VARIABLE &&
151       expr->AsVariableProxy()->var()->IsUnallocated()) ||
152      assign_type == NAMED_PROPERTY || assign_type == KEYED_PROPERTY) {
153    // TODO(ishell): consider using ICSlotCache for variables here.
154    FeedbackVectorSlotKind kind = assign_type == KEYED_PROPERTY
155                                      ? FeedbackVectorSlotKind::KEYED_STORE_IC
156                                      : FeedbackVectorSlotKind::STORE_IC;
157    *out_slot = spec->AddSlot(kind);
158  }
159}
160
161void ForInStatement::AssignFeedbackVectorSlots(Isolate* isolate,
162                                               FeedbackVectorSpec* spec,
163                                               FeedbackVectorSlotCache* cache) {
164  AssignVectorSlots(each(), spec, &each_slot_);
165  for_in_feedback_slot_ = spec->AddGeneralSlot();
166}
167
168
169Assignment::Assignment(Zone* zone, Token::Value op, Expression* target,
170                       Expression* value, int pos)
171    : Expression(zone, pos),
172      bit_field_(
173          IsUninitializedField::encode(false) | KeyTypeField::encode(ELEMENT) |
174          StoreModeField::encode(STANDARD_STORE) | TokenField::encode(op)),
175      target_(target),
176      value_(value),
177      binary_operation_(NULL) {}
178
179
180void Assignment::AssignFeedbackVectorSlots(Isolate* isolate,
181                                           FeedbackVectorSpec* spec,
182                                           FeedbackVectorSlotCache* cache) {
183  AssignVectorSlots(target(), spec, &slot_);
184}
185
186
187void CountOperation::AssignFeedbackVectorSlots(Isolate* isolate,
188                                               FeedbackVectorSpec* spec,
189                                               FeedbackVectorSlotCache* cache) {
190  AssignVectorSlots(expression(), spec, &slot_);
191}
192
193
194Token::Value Assignment::binary_op() const {
195  switch (op()) {
196    case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
197    case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
198    case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
199    case Token::ASSIGN_SHL: return Token::SHL;
200    case Token::ASSIGN_SAR: return Token::SAR;
201    case Token::ASSIGN_SHR: return Token::SHR;
202    case Token::ASSIGN_ADD: return Token::ADD;
203    case Token::ASSIGN_SUB: return Token::SUB;
204    case Token::ASSIGN_MUL: return Token::MUL;
205    case Token::ASSIGN_DIV: return Token::DIV;
206    case Token::ASSIGN_MOD: return Token::MOD;
207    default: UNREACHABLE();
208  }
209  return Token::ILLEGAL;
210}
211
212
213bool FunctionLiteral::AllowsLazyCompilation() {
214  return scope()->AllowsLazyCompilation();
215}
216
217
218bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
219  return scope()->AllowsLazyCompilationWithoutContext();
220}
221
222
223int FunctionLiteral::start_position() const {
224  return scope()->start_position();
225}
226
227
228int FunctionLiteral::end_position() const {
229  return scope()->end_position();
230}
231
232
233LanguageMode FunctionLiteral::language_mode() const {
234  return scope()->language_mode();
235}
236
237
238bool FunctionLiteral::NeedsHomeObject(Expression* expr) {
239  if (expr == nullptr || !expr->IsFunctionLiteral()) return false;
240  DCHECK_NOT_NULL(expr->AsFunctionLiteral()->scope());
241  return expr->AsFunctionLiteral()->scope()->NeedsHomeObject();
242}
243
244
245ObjectLiteralProperty::ObjectLiteralProperty(Expression* key, Expression* value,
246                                             Kind kind, bool is_static,
247                                             bool is_computed_name)
248    : key_(key),
249      value_(value),
250      kind_(kind),
251      emit_store_(true),
252      is_static_(is_static),
253      is_computed_name_(is_computed_name) {}
254
255
256ObjectLiteralProperty::ObjectLiteralProperty(AstValueFactory* ast_value_factory,
257                                             Expression* key, Expression* value,
258                                             bool is_static,
259                                             bool is_computed_name)
260    : key_(key),
261      value_(value),
262      emit_store_(true),
263      is_static_(is_static),
264      is_computed_name_(is_computed_name) {
265  if (!is_computed_name &&
266      key->AsLiteral()->raw_value()->EqualsString(
267          ast_value_factory->proto_string())) {
268    kind_ = PROTOTYPE;
269  } else if (value_->AsMaterializedLiteral() != NULL) {
270    kind_ = MATERIALIZED_LITERAL;
271  } else if (value_->IsLiteral()) {
272    kind_ = CONSTANT;
273  } else {
274    kind_ = COMPUTED;
275  }
276}
277
278bool ObjectLiteralProperty::NeedsSetFunctionName() const {
279  return is_computed_name_ &&
280         (value_->IsAnonymousFunctionDefinition() ||
281          (value_->IsFunctionLiteral() &&
282           IsConciseMethod(value_->AsFunctionLiteral()->kind())));
283}
284
285void ClassLiteral::AssignFeedbackVectorSlots(Isolate* isolate,
286                                             FeedbackVectorSpec* spec,
287                                             FeedbackVectorSlotCache* cache) {
288  // This logic that computes the number of slots needed for vector store
289  // ICs must mirror FullCodeGenerator::VisitClassLiteral.
290  prototype_slot_ = spec->AddLoadICSlot();
291  if (NeedsProxySlot()) {
292    proxy_slot_ = spec->AddStoreICSlot();
293  }
294
295  for (int i = 0; i < properties()->length(); i++) {
296    ObjectLiteral::Property* property = properties()->at(i);
297    Expression* value = property->value();
298    if (FunctionLiteral::NeedsHomeObject(value)) {
299      property->SetSlot(spec->AddStoreICSlot());
300    }
301  }
302}
303
304
305bool ObjectLiteral::Property::IsCompileTimeValue() {
306  return kind_ == CONSTANT ||
307      (kind_ == MATERIALIZED_LITERAL &&
308       CompileTimeValue::IsCompileTimeValue(value_));
309}
310
311
312void ObjectLiteral::Property::set_emit_store(bool emit_store) {
313  emit_store_ = emit_store;
314}
315
316
317bool ObjectLiteral::Property::emit_store() {
318  return emit_store_;
319}
320
321
322void ObjectLiteral::AssignFeedbackVectorSlots(Isolate* isolate,
323                                              FeedbackVectorSpec* spec,
324                                              FeedbackVectorSlotCache* cache) {
325  // This logic that computes the number of slots needed for vector store
326  // ics must mirror FullCodeGenerator::VisitObjectLiteral.
327  int property_index = 0;
328  for (; property_index < properties()->length(); property_index++) {
329    ObjectLiteral::Property* property = properties()->at(property_index);
330    if (property->is_computed_name()) break;
331    if (property->IsCompileTimeValue()) continue;
332
333    Literal* key = property->key()->AsLiteral();
334    Expression* value = property->value();
335    switch (property->kind()) {
336      case ObjectLiteral::Property::CONSTANT:
337        UNREACHABLE();
338      case ObjectLiteral::Property::MATERIALIZED_LITERAL:
339      // Fall through.
340      case ObjectLiteral::Property::COMPUTED:
341        // It is safe to use [[Put]] here because the boilerplate already
342        // contains computed properties with an uninitialized value.
343        if (key->value()->IsInternalizedString()) {
344          if (property->emit_store()) {
345            property->SetSlot(spec->AddStoreICSlot());
346            if (FunctionLiteral::NeedsHomeObject(value)) {
347              property->SetSlot(spec->AddStoreICSlot(), 1);
348            }
349          }
350          break;
351        }
352        if (property->emit_store() && FunctionLiteral::NeedsHomeObject(value)) {
353          property->SetSlot(spec->AddStoreICSlot());
354        }
355        break;
356      case ObjectLiteral::Property::PROTOTYPE:
357        break;
358      case ObjectLiteral::Property::GETTER:
359        if (property->emit_store() && FunctionLiteral::NeedsHomeObject(value)) {
360          property->SetSlot(spec->AddStoreICSlot());
361        }
362        break;
363      case ObjectLiteral::Property::SETTER:
364        if (property->emit_store() && FunctionLiteral::NeedsHomeObject(value)) {
365          property->SetSlot(spec->AddStoreICSlot());
366        }
367        break;
368    }
369  }
370
371  for (; property_index < properties()->length(); property_index++) {
372    ObjectLiteral::Property* property = properties()->at(property_index);
373
374    Expression* value = property->value();
375    if (property->kind() != ObjectLiteral::Property::PROTOTYPE) {
376      if (FunctionLiteral::NeedsHomeObject(value)) {
377        property->SetSlot(spec->AddStoreICSlot());
378      }
379    }
380  }
381}
382
383
384void ObjectLiteral::CalculateEmitStore(Zone* zone) {
385  const auto GETTER = ObjectLiteral::Property::GETTER;
386  const auto SETTER = ObjectLiteral::Property::SETTER;
387
388  ZoneAllocationPolicy allocator(zone);
389
390  ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity,
391                    allocator);
392  for (int i = properties()->length() - 1; i >= 0; i--) {
393    ObjectLiteral::Property* property = properties()->at(i);
394    if (property->is_computed_name()) continue;
395    if (property->kind() == ObjectLiteral::Property::PROTOTYPE) continue;
396    Literal* literal = property->key()->AsLiteral();
397    DCHECK(!literal->IsNullLiteral());
398
399    // If there is an existing entry do not emit a store unless the previous
400    // entry was also an accessor.
401    uint32_t hash = literal->Hash();
402    ZoneHashMap::Entry* entry = table.LookupOrInsert(literal, hash, allocator);
403    if (entry->value != NULL) {
404      auto previous_kind =
405          static_cast<ObjectLiteral::Property*>(entry->value)->kind();
406      if (!((property->kind() == GETTER && previous_kind == SETTER) ||
407            (property->kind() == SETTER && previous_kind == GETTER))) {
408        property->set_emit_store(false);
409      }
410    }
411    entry->value = property;
412  }
413}
414
415
416bool ObjectLiteral::IsBoilerplateProperty(ObjectLiteral::Property* property) {
417  return property != NULL &&
418         property->kind() != ObjectLiteral::Property::PROTOTYPE;
419}
420
421
422void ObjectLiteral::BuildConstantProperties(Isolate* isolate) {
423  if (!constant_properties_.is_null()) return;
424
425  // Allocate a fixed array to hold all the constant properties.
426  Handle<FixedArray> constant_properties = isolate->factory()->NewFixedArray(
427      boilerplate_properties_ * 2, TENURED);
428
429  int position = 0;
430  // Accumulate the value in local variables and store it at the end.
431  bool is_simple = true;
432  int depth_acc = 1;
433  uint32_t max_element_index = 0;
434  uint32_t elements = 0;
435  for (int i = 0; i < properties()->length(); i++) {
436    ObjectLiteral::Property* property = properties()->at(i);
437    if (!IsBoilerplateProperty(property)) {
438      is_simple = false;
439      continue;
440    }
441
442    if (position == boilerplate_properties_ * 2) {
443      DCHECK(property->is_computed_name());
444      is_simple = false;
445      break;
446    }
447    DCHECK(!property->is_computed_name());
448
449    MaterializedLiteral* m_literal = property->value()->AsMaterializedLiteral();
450    if (m_literal != NULL) {
451      m_literal->BuildConstants(isolate);
452      if (m_literal->depth() >= depth_acc) depth_acc = m_literal->depth() + 1;
453    }
454
455    // Add CONSTANT and COMPUTED properties to boilerplate. Use undefined
456    // value for COMPUTED properties, the real value is filled in at
457    // runtime. The enumeration order is maintained.
458    Handle<Object> key = property->key()->AsLiteral()->value();
459    Handle<Object> value = GetBoilerplateValue(property->value(), isolate);
460
461    // Ensure objects that may, at any point in time, contain fields with double
462    // representation are always treated as nested objects. This is true for
463    // computed fields (value is undefined), and smi and double literals
464    // (value->IsNumber()).
465    // TODO(verwaest): Remove once we can store them inline.
466    if (FLAG_track_double_fields &&
467        (value->IsNumber() || value->IsUninitialized(isolate))) {
468      may_store_doubles_ = true;
469    }
470
471    is_simple = is_simple && !value->IsUninitialized(isolate);
472
473    // Keep track of the number of elements in the object literal and
474    // the largest element index.  If the largest element index is
475    // much larger than the number of elements, creating an object
476    // literal with fast elements will be a waste of space.
477    uint32_t element_index = 0;
478    if (key->IsString() && String::cast(*key)->AsArrayIndex(&element_index)) {
479      max_element_index = Max(element_index, max_element_index);
480      elements++;
481      key = isolate->factory()->NewNumberFromUint(element_index);
482    } else if (key->ToArrayIndex(&element_index)) {
483      max_element_index = Max(element_index, max_element_index);
484      elements++;
485    } else if (key->IsNumber()) {
486      key = isolate->factory()->NumberToString(key);
487    }
488
489    // Add name, value pair to the fixed array.
490    constant_properties->set(position++, *key);
491    constant_properties->set(position++, *value);
492  }
493
494  constant_properties_ = constant_properties;
495  fast_elements_ =
496      (max_element_index <= 32) || ((2 * elements) >= max_element_index);
497  has_elements_ = elements > 0;
498  set_is_simple(is_simple);
499  set_depth(depth_acc);
500}
501
502
503void ArrayLiteral::BuildConstantElements(Isolate* isolate) {
504  DCHECK_LT(first_spread_index_, 0);
505
506  if (!constant_elements_.is_null()) return;
507
508  int constants_length = values()->length();
509
510  // Allocate a fixed array to hold all the object literals.
511  Handle<JSArray> array = isolate->factory()->NewJSArray(
512      FAST_HOLEY_SMI_ELEMENTS, constants_length, constants_length,
513      INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);
514
515  // Fill in the literals.
516  bool is_simple = true;
517  int depth_acc = 1;
518  bool is_holey = false;
519  int array_index = 0;
520  for (; array_index < constants_length; array_index++) {
521    Expression* element = values()->at(array_index);
522    DCHECK(!element->IsSpread());
523    MaterializedLiteral* m_literal = element->AsMaterializedLiteral();
524    if (m_literal != NULL) {
525      m_literal->BuildConstants(isolate);
526      if (m_literal->depth() + 1 > depth_acc) {
527        depth_acc = m_literal->depth() + 1;
528      }
529    }
530
531    // New handle scope here, needs to be after BuildContants().
532    HandleScope scope(isolate);
533    Handle<Object> boilerplate_value = GetBoilerplateValue(element, isolate);
534    if (boilerplate_value->IsTheHole(isolate)) {
535      is_holey = true;
536      continue;
537    }
538
539    if (boilerplate_value->IsUninitialized(isolate)) {
540      boilerplate_value = handle(Smi::FromInt(0), isolate);
541      is_simple = false;
542    }
543
544    JSObject::AddDataElement(array, array_index, boilerplate_value, NONE)
545        .Assert();
546  }
547
548  JSObject::ValidateElements(array);
549  Handle<FixedArrayBase> element_values(array->elements());
550
551  // Simple and shallow arrays can be lazily copied, we transform the
552  // elements array to a copy-on-write array.
553  if (is_simple && depth_acc == 1 && array_index > 0 &&
554      array->HasFastSmiOrObjectElements()) {
555    element_values->set_map(isolate->heap()->fixed_cow_array_map());
556  }
557
558  // Remember both the literal's constant values as well as the ElementsKind
559  // in a 2-element FixedArray.
560  Handle<FixedArray> literals = isolate->factory()->NewFixedArray(2, TENURED);
561
562  ElementsKind kind = array->GetElementsKind();
563  kind = is_holey ? GetHoleyElementsKind(kind) : GetPackedElementsKind(kind);
564
565  literals->set(0, Smi::FromInt(kind));
566  literals->set(1, *element_values);
567
568  constant_elements_ = literals;
569  set_is_simple(is_simple);
570  set_depth(depth_acc);
571}
572
573
574void ArrayLiteral::AssignFeedbackVectorSlots(Isolate* isolate,
575                                             FeedbackVectorSpec* spec,
576                                             FeedbackVectorSlotCache* cache) {
577  // This logic that computes the number of slots needed for vector store
578  // ics must mirror FullCodeGenerator::VisitArrayLiteral.
579  int array_index = 0;
580  for (; array_index < values()->length(); array_index++) {
581    Expression* subexpr = values()->at(array_index);
582    DCHECK(!subexpr->IsSpread());
583    if (CompileTimeValue::IsCompileTimeValue(subexpr)) continue;
584
585    // We'll reuse the same literal slot for all of the non-constant
586    // subexpressions that use a keyed store IC.
587    literal_slot_ = spec->AddKeyedStoreICSlot();
588    return;
589  }
590}
591
592
593Handle<Object> MaterializedLiteral::GetBoilerplateValue(Expression* expression,
594                                                        Isolate* isolate) {
595  if (expression->IsLiteral()) {
596    return expression->AsLiteral()->value();
597  }
598  if (CompileTimeValue::IsCompileTimeValue(expression)) {
599    return CompileTimeValue::GetValue(isolate, expression);
600  }
601  return isolate->factory()->uninitialized_value();
602}
603
604
605void MaterializedLiteral::BuildConstants(Isolate* isolate) {
606  if (IsArrayLiteral()) {
607    return AsArrayLiteral()->BuildConstantElements(isolate);
608  }
609  if (IsObjectLiteral()) {
610    return AsObjectLiteral()->BuildConstantProperties(isolate);
611  }
612  DCHECK(IsRegExpLiteral());
613  DCHECK(depth() >= 1);  // Depth should be initialized.
614}
615
616
617void UnaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
618  // TODO(olivf) If this Operation is used in a test context, then the
619  // expression has a ToBoolean stub and we want to collect the type
620  // information. However the GraphBuilder expects it to be on the instruction
621  // corresponding to the TestContext, therefore we have to store it here and
622  // not on the operand.
623  set_to_boolean_types(oracle->ToBooleanTypes(expression()->test_id()));
624}
625
626
627void BinaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
628  // TODO(olivf) If this Operation is used in a test context, then the right
629  // hand side has a ToBoolean stub and we want to collect the type information.
630  // However the GraphBuilder expects it to be on the instruction corresponding
631  // to the TestContext, therefore we have to store it here and not on the
632  // right hand operand.
633  set_to_boolean_types(oracle->ToBooleanTypes(right()->test_id()));
634}
635
636
637static bool IsTypeof(Expression* expr) {
638  UnaryOperation* maybe_unary = expr->AsUnaryOperation();
639  return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF;
640}
641
642
643// Check for the pattern: typeof <expression> equals <string literal>.
644static bool MatchLiteralCompareTypeof(Expression* left,
645                                      Token::Value op,
646                                      Expression* right,
647                                      Expression** expr,
648                                      Handle<String>* check) {
649  if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) {
650    *expr = left->AsUnaryOperation()->expression();
651    *check = Handle<String>::cast(right->AsLiteral()->value());
652    return true;
653  }
654  return false;
655}
656
657
658bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
659                                              Handle<String>* check) {
660  return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) ||
661      MatchLiteralCompareTypeof(right_, op_, left_, expr, check);
662}
663
664
665static bool IsVoidOfLiteral(Expression* expr) {
666  UnaryOperation* maybe_unary = expr->AsUnaryOperation();
667  return maybe_unary != NULL &&
668      maybe_unary->op() == Token::VOID &&
669      maybe_unary->expression()->IsLiteral();
670}
671
672
673// Check for the pattern: void <literal> equals <expression> or
674// undefined equals <expression>
675static bool MatchLiteralCompareUndefined(Expression* left,
676                                         Token::Value op,
677                                         Expression* right,
678                                         Expression** expr) {
679  if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) {
680    *expr = right;
681    return true;
682  }
683  if (left->IsUndefinedLiteral() && Token::IsEqualityOp(op)) {
684    *expr = right;
685    return true;
686  }
687  return false;
688}
689
690bool CompareOperation::IsLiteralCompareUndefined(Expression** expr) {
691  return MatchLiteralCompareUndefined(left_, op_, right_, expr) ||
692         MatchLiteralCompareUndefined(right_, op_, left_, expr);
693}
694
695
696// Check for the pattern: null equals <expression>
697static bool MatchLiteralCompareNull(Expression* left,
698                                    Token::Value op,
699                                    Expression* right,
700                                    Expression** expr) {
701  if (left->IsNullLiteral() && Token::IsEqualityOp(op)) {
702    *expr = right;
703    return true;
704  }
705  return false;
706}
707
708
709bool CompareOperation::IsLiteralCompareNull(Expression** expr) {
710  return MatchLiteralCompareNull(left_, op_, right_, expr) ||
711      MatchLiteralCompareNull(right_, op_, left_, expr);
712}
713
714
715// ----------------------------------------------------------------------------
716// Inlining support
717
718bool Declaration::IsInlineable() const {
719  return proxy()->var()->IsStackAllocated();
720}
721
722bool FunctionDeclaration::IsInlineable() const {
723  return false;
724}
725
726
727// ----------------------------------------------------------------------------
728// Recording of type feedback
729
730// TODO(rossberg): all RecordTypeFeedback functions should disappear
731// once we use the common type field in the AST consistently.
732
733void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
734  set_to_boolean_types(oracle->ToBooleanTypes(test_id()));
735}
736
737
738bool Call::IsUsingCallFeedbackICSlot(Isolate* isolate) const {
739  CallType call_type = GetCallType(isolate);
740  if (call_type == POSSIBLY_EVAL_CALL) {
741    return false;
742  }
743  return true;
744}
745
746
747bool Call::IsUsingCallFeedbackSlot(Isolate* isolate) const {
748  // SuperConstructorCall uses a CallConstructStub, which wants
749  // a Slot, in addition to any IC slots requested elsewhere.
750  return GetCallType(isolate) == SUPER_CALL;
751}
752
753
754void Call::AssignFeedbackVectorSlots(Isolate* isolate, FeedbackVectorSpec* spec,
755                                     FeedbackVectorSlotCache* cache) {
756  if (IsUsingCallFeedbackICSlot(isolate)) {
757    ic_slot_ = spec->AddCallICSlot();
758  }
759  if (IsUsingCallFeedbackSlot(isolate)) {
760    stub_slot_ = spec->AddGeneralSlot();
761  }
762}
763
764
765Call::CallType Call::GetCallType(Isolate* isolate) const {
766  VariableProxy* proxy = expression()->AsVariableProxy();
767  if (proxy != NULL) {
768    if (proxy->var()->is_possibly_eval(isolate)) {
769      return POSSIBLY_EVAL_CALL;
770    } else if (proxy->var()->IsUnallocatedOrGlobalSlot()) {
771      return GLOBAL_CALL;
772    } else if (proxy->var()->IsLookupSlot()) {
773      return LOOKUP_SLOT_CALL;
774    }
775  }
776
777  if (expression()->IsSuperCallReference()) return SUPER_CALL;
778
779  Property* property = expression()->AsProperty();
780  if (property != nullptr) {
781    bool is_super = property->IsSuperAccess();
782    if (property->key()->IsPropertyName()) {
783      return is_super ? NAMED_SUPER_PROPERTY_CALL : NAMED_PROPERTY_CALL;
784    } else {
785      return is_super ? KEYED_SUPER_PROPERTY_CALL : KEYED_PROPERTY_CALL;
786    }
787  }
788
789  return OTHER_CALL;
790}
791
792
793// ----------------------------------------------------------------------------
794// Implementation of AstVisitor
795
796void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
797  for (int i = 0; i < declarations->length(); i++) {
798    Visit(declarations->at(i));
799  }
800}
801
802
803void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
804  for (int i = 0; i < statements->length(); i++) {
805    Statement* stmt = statements->at(i);
806    Visit(stmt);
807    if (stmt->IsJump()) break;
808  }
809}
810
811
812void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
813  for (int i = 0; i < expressions->length(); i++) {
814    // The variable statement visiting code may pass NULL expressions
815    // to this code. Maybe this should be handled by introducing an
816    // undefined expression or literal?  Revisit this code if this
817    // changes
818    Expression* expression = expressions->at(i);
819    if (expression != NULL) Visit(expression);
820  }
821}
822
823// ----------------------------------------------------------------------------
824// Implementation of AstTraversalVisitor
825
826#define RECURSE(call)               \
827  do {                              \
828    DCHECK(!HasStackOverflow());    \
829    call;                           \
830    if (HasStackOverflow()) return; \
831  } while (false)
832
833#define RECURSE_EXPRESSION(call)    \
834  do {                              \
835    DCHECK(!HasStackOverflow());    \
836    ++depth_;                       \
837    call;                           \
838    --depth_;                       \
839    if (HasStackOverflow()) return; \
840  } while (false)
841
842AstTraversalVisitor::AstTraversalVisitor(Isolate* isolate) : depth_(0) {
843  InitializeAstVisitor(isolate);
844}
845
846AstTraversalVisitor::AstTraversalVisitor(uintptr_t stack_limit) : depth_(0) {
847  InitializeAstVisitor(stack_limit);
848}
849
850void AstTraversalVisitor::VisitDeclarations(ZoneList<Declaration*>* decls) {
851  for (int i = 0; i < decls->length(); ++i) {
852    Declaration* decl = decls->at(i);
853    RECURSE(Visit(decl));
854  }
855}
856
857void AstTraversalVisitor::VisitStatements(ZoneList<Statement*>* stmts) {
858  for (int i = 0; i < stmts->length(); ++i) {
859    Statement* stmt = stmts->at(i);
860    RECURSE(Visit(stmt));
861    if (stmt->IsJump()) break;
862  }
863}
864
865void AstTraversalVisitor::VisitVariableDeclaration(VariableDeclaration* decl) {}
866
867void AstTraversalVisitor::VisitFunctionDeclaration(FunctionDeclaration* decl) {
868  RECURSE(Visit(decl->fun()));
869}
870
871void AstTraversalVisitor::VisitImportDeclaration(ImportDeclaration* decl) {}
872
873void AstTraversalVisitor::VisitExportDeclaration(ExportDeclaration* decl) {}
874
875void AstTraversalVisitor::VisitBlock(Block* stmt) {
876  RECURSE(VisitStatements(stmt->statements()));
877}
878
879void AstTraversalVisitor::VisitExpressionStatement(ExpressionStatement* stmt) {
880  RECURSE(Visit(stmt->expression()));
881}
882
883void AstTraversalVisitor::VisitEmptyStatement(EmptyStatement* stmt) {}
884
885void AstTraversalVisitor::VisitSloppyBlockFunctionStatement(
886    SloppyBlockFunctionStatement* stmt) {
887  RECURSE(Visit(stmt->statement()));
888}
889
890void AstTraversalVisitor::VisitIfStatement(IfStatement* stmt) {
891  RECURSE(Visit(stmt->condition()));
892  RECURSE(Visit(stmt->then_statement()));
893  RECURSE(Visit(stmt->else_statement()));
894}
895
896void AstTraversalVisitor::VisitContinueStatement(ContinueStatement* stmt) {}
897
898void AstTraversalVisitor::VisitBreakStatement(BreakStatement* stmt) {}
899
900void AstTraversalVisitor::VisitReturnStatement(ReturnStatement* stmt) {
901  RECURSE(Visit(stmt->expression()));
902}
903
904void AstTraversalVisitor::VisitWithStatement(WithStatement* stmt) {
905  RECURSE(stmt->expression());
906  RECURSE(stmt->statement());
907}
908
909void AstTraversalVisitor::VisitSwitchStatement(SwitchStatement* stmt) {
910  RECURSE(Visit(stmt->tag()));
911
912  ZoneList<CaseClause*>* clauses = stmt->cases();
913
914  for (int i = 0; i < clauses->length(); ++i) {
915    CaseClause* clause = clauses->at(i);
916    if (!clause->is_default()) {
917      Expression* label = clause->label();
918      RECURSE(Visit(label));
919    }
920    ZoneList<Statement*>* stmts = clause->statements();
921    RECURSE(VisitStatements(stmts));
922  }
923}
924
925void AstTraversalVisitor::VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
926
927void AstTraversalVisitor::VisitDoWhileStatement(DoWhileStatement* stmt) {
928  RECURSE(Visit(stmt->body()));
929  RECURSE(Visit(stmt->cond()));
930}
931
932void AstTraversalVisitor::VisitWhileStatement(WhileStatement* stmt) {
933  RECURSE(Visit(stmt->cond()));
934  RECURSE(Visit(stmt->body()));
935}
936
937void AstTraversalVisitor::VisitForStatement(ForStatement* stmt) {
938  if (stmt->init() != NULL) {
939    RECURSE(Visit(stmt->init()));
940  }
941  if (stmt->cond() != NULL) {
942    RECURSE(Visit(stmt->cond()));
943  }
944  if (stmt->next() != NULL) {
945    RECURSE(Visit(stmt->next()));
946  }
947  RECURSE(Visit(stmt->body()));
948}
949
950void AstTraversalVisitor::VisitForInStatement(ForInStatement* stmt) {
951  RECURSE(Visit(stmt->enumerable()));
952  RECURSE(Visit(stmt->body()));
953}
954
955void AstTraversalVisitor::VisitForOfStatement(ForOfStatement* stmt) {
956  RECURSE(Visit(stmt->assign_iterator()));
957  RECURSE(Visit(stmt->next_result()));
958  RECURSE(Visit(stmt->result_done()));
959  RECURSE(Visit(stmt->assign_each()));
960  RECURSE(Visit(stmt->body()));
961}
962
963void AstTraversalVisitor::VisitTryCatchStatement(TryCatchStatement* stmt) {
964  RECURSE(Visit(stmt->try_block()));
965  RECURSE(Visit(stmt->catch_block()));
966}
967
968void AstTraversalVisitor::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
969  RECURSE(Visit(stmt->try_block()));
970  RECURSE(Visit(stmt->finally_block()));
971}
972
973void AstTraversalVisitor::VisitDebuggerStatement(DebuggerStatement* stmt) {}
974
975void AstTraversalVisitor::VisitFunctionLiteral(FunctionLiteral* expr) {
976  Scope* scope = expr->scope();
977  RECURSE_EXPRESSION(VisitDeclarations(scope->declarations()));
978  RECURSE_EXPRESSION(VisitStatements(expr->body()));
979}
980
981void AstTraversalVisitor::VisitNativeFunctionLiteral(
982    NativeFunctionLiteral* expr) {}
983
984void AstTraversalVisitor::VisitDoExpression(DoExpression* expr) {
985  RECURSE(VisitBlock(expr->block()));
986  RECURSE(VisitVariableProxy(expr->result()));
987}
988
989void AstTraversalVisitor::VisitConditional(Conditional* expr) {
990  RECURSE_EXPRESSION(Visit(expr->condition()));
991  RECURSE_EXPRESSION(Visit(expr->then_expression()));
992  RECURSE_EXPRESSION(Visit(expr->else_expression()));
993}
994
995void AstTraversalVisitor::VisitVariableProxy(VariableProxy* expr) {}
996
997void AstTraversalVisitor::VisitLiteral(Literal* expr) {}
998
999void AstTraversalVisitor::VisitRegExpLiteral(RegExpLiteral* expr) {}
1000
1001void AstTraversalVisitor::VisitObjectLiteral(ObjectLiteral* expr) {
1002  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
1003  for (int i = 0; i < props->length(); ++i) {
1004    ObjectLiteralProperty* prop = props->at(i);
1005    if (!prop->key()->IsLiteral()) {
1006      RECURSE_EXPRESSION(Visit(prop->key()));
1007    }
1008    RECURSE_EXPRESSION(Visit(prop->value()));
1009  }
1010}
1011
1012void AstTraversalVisitor::VisitArrayLiteral(ArrayLiteral* expr) {
1013  ZoneList<Expression*>* values = expr->values();
1014  for (int i = 0; i < values->length(); ++i) {
1015    Expression* value = values->at(i);
1016    RECURSE_EXPRESSION(Visit(value));
1017  }
1018}
1019
1020void AstTraversalVisitor::VisitAssignment(Assignment* expr) {
1021  RECURSE_EXPRESSION(Visit(expr->target()));
1022  RECURSE_EXPRESSION(Visit(expr->value()));
1023}
1024
1025void AstTraversalVisitor::VisitYield(Yield* expr) {
1026  RECURSE_EXPRESSION(Visit(expr->generator_object()));
1027  RECURSE_EXPRESSION(Visit(expr->expression()));
1028}
1029
1030void AstTraversalVisitor::VisitThrow(Throw* expr) {
1031  RECURSE_EXPRESSION(Visit(expr->exception()));
1032}
1033
1034void AstTraversalVisitor::VisitProperty(Property* expr) {
1035  RECURSE_EXPRESSION(Visit(expr->obj()));
1036  RECURSE_EXPRESSION(Visit(expr->key()));
1037}
1038
1039void AstTraversalVisitor::VisitCall(Call* expr) {
1040  RECURSE_EXPRESSION(Visit(expr->expression()));
1041  ZoneList<Expression*>* args = expr->arguments();
1042  for (int i = 0; i < args->length(); ++i) {
1043    Expression* arg = args->at(i);
1044    RECURSE_EXPRESSION(Visit(arg));
1045  }
1046}
1047
1048void AstTraversalVisitor::VisitCallNew(CallNew* expr) {
1049  RECURSE_EXPRESSION(Visit(expr->expression()));
1050  ZoneList<Expression*>* args = expr->arguments();
1051  for (int i = 0; i < args->length(); ++i) {
1052    Expression* arg = args->at(i);
1053    RECURSE_EXPRESSION(Visit(arg));
1054  }
1055}
1056
1057void AstTraversalVisitor::VisitCallRuntime(CallRuntime* expr) {
1058  ZoneList<Expression*>* args = expr->arguments();
1059  for (int i = 0; i < args->length(); ++i) {
1060    Expression* arg = args->at(i);
1061    RECURSE_EXPRESSION(Visit(arg));
1062  }
1063}
1064
1065void AstTraversalVisitor::VisitUnaryOperation(UnaryOperation* expr) {
1066  RECURSE_EXPRESSION(Visit(expr->expression()));
1067}
1068
1069void AstTraversalVisitor::VisitCountOperation(CountOperation* expr) {
1070  RECURSE_EXPRESSION(Visit(expr->expression()));
1071}
1072
1073void AstTraversalVisitor::VisitBinaryOperation(BinaryOperation* expr) {
1074  RECURSE_EXPRESSION(Visit(expr->left()));
1075  RECURSE_EXPRESSION(Visit(expr->right()));
1076}
1077
1078void AstTraversalVisitor::VisitCompareOperation(CompareOperation* expr) {
1079  RECURSE_EXPRESSION(Visit(expr->left()));
1080  RECURSE_EXPRESSION(Visit(expr->right()));
1081}
1082
1083void AstTraversalVisitor::VisitThisFunction(ThisFunction* expr) {}
1084
1085void AstTraversalVisitor::VisitClassLiteral(ClassLiteral* expr) {
1086  if (expr->extends() != nullptr) {
1087    RECURSE_EXPRESSION(Visit(expr->extends()));
1088  }
1089  RECURSE_EXPRESSION(Visit(expr->constructor()));
1090  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
1091  for (int i = 0; i < props->length(); ++i) {
1092    ObjectLiteralProperty* prop = props->at(i);
1093    if (!prop->key()->IsLiteral()) {
1094      RECURSE_EXPRESSION(Visit(prop->key()));
1095    }
1096    RECURSE_EXPRESSION(Visit(prop->value()));
1097  }
1098}
1099
1100void AstTraversalVisitor::VisitSpread(Spread* expr) {
1101  RECURSE_EXPRESSION(Visit(expr->expression()));
1102}
1103
1104void AstTraversalVisitor::VisitEmptyParentheses(EmptyParentheses* expr) {}
1105
1106void AstTraversalVisitor::VisitSuperPropertyReference(
1107    SuperPropertyReference* expr) {
1108  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
1109  RECURSE_EXPRESSION(Visit(expr->home_object()));
1110}
1111
1112void AstTraversalVisitor::VisitSuperCallReference(SuperCallReference* expr) {
1113  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
1114  RECURSE_EXPRESSION(VisitVariableProxy(expr->new_target_var()));
1115  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_function_var()));
1116}
1117
1118void AstTraversalVisitor::VisitRewritableExpression(
1119    RewritableExpression* expr) {
1120  RECURSE(Visit(expr->expression()));
1121}
1122
1123#undef RECURSE_EXPRESSION
1124#undef RECURSE
1125
1126CaseClause::CaseClause(Zone* zone, Expression* label,
1127                       ZoneList<Statement*>* statements, int pos)
1128    : Expression(zone, pos),
1129      label_(label),
1130      statements_(statements),
1131      compare_type_(Type::None()) {}
1132
1133uint32_t Literal::Hash() {
1134  return raw_value()->IsString()
1135             ? raw_value()->AsString()->hash()
1136             : ComputeLongHash(double_to_uint64(raw_value()->AsNumber()));
1137}
1138
1139
1140// static
1141bool Literal::Match(void* literal1, void* literal2) {
1142  const AstValue* x = static_cast<Literal*>(literal1)->raw_value();
1143  const AstValue* y = static_cast<Literal*>(literal2)->raw_value();
1144  return (x->IsString() && y->IsString() && x->AsString() == y->AsString()) ||
1145         (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber());
1146}
1147
1148
1149}  // namespace internal
1150}  // namespace v8
1151