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