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