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