ast.cc revision 1e0659c275bb392c045087af4f6b0d7565cb3d77 
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
39unsigned AstNode::current_id_ = 0;
40unsigned AstNode::count_ = 0;
41VariableProxySentinel VariableProxySentinel::this_proxy_(true);
42VariableProxySentinel VariableProxySentinel::identifier_proxy_(false);
43ValidLeftHandSideSentinel ValidLeftHandSideSentinel::instance_;
44Property Property::this_property_(VariableProxySentinel::this_proxy(), NULL, 0);
45Call Call::sentinel_(NULL, NULL, 0);
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    if (handle->IsSymbol()) {
253      Handle<String> name(String::cast(*handle));
254      if (name->AsArrayIndex(&hash)) {
255        Handle<Object> key_handle = Factory::NewNumberFromUint(hash);
256        key = key_handle.location();
257        table = &elements;
258      } else {
259        key = name.location();
260        hash = name->Hash();
261        table = &properties;
262      }
263    } else if (handle->ToArrayIndex(&hash)) {
264      key = handle.location();
265      table = &elements;
266    } else {
267      ASSERT(handle->IsNumber());
268      double num = handle->Number();
269      char arr[100];
270      Vector<char> buffer(arr, ARRAY_SIZE(arr));
271      const char* str = DoubleToCString(num, buffer);
272      Handle<String> name = Factory::NewStringFromAscii(CStrVector(str));
273      key = name.location();
274      hash = name->Hash();
275      table = &properties;
276    }
277    // If the key of a computed property is in the table, do not emit
278    // a store for the property later.
279    if (property->kind() == ObjectLiteral::Property::COMPUTED) {
280      if (table->Lookup(key, hash, false) != NULL) {
281        property->set_emit_store(false);
282      }
283    }
284    // Add key to the table.
285    table->Lookup(key, hash, true);
286  }
287}
288
289
290void TargetCollector::AddTarget(BreakTarget* target) {
291  // Add the label to the collector, but discard duplicates.
292  int length = targets_->length();
293  for (int i = 0; i < length; i++) {
294    if (targets_->at(i) == target) return;
295  }
296  targets_->Add(target);
297}
298
299
300bool Expression::GuaranteedSmiResult() {
301  BinaryOperation* node = AsBinaryOperation();
302  if (node == NULL) return false;
303  Token::Value op = node->op();
304  switch (op) {
305    case Token::COMMA:
306    case Token::OR:
307    case Token::AND:
308    case Token::ADD:
309    case Token::SUB:
310    case Token::MUL:
311    case Token::DIV:
312    case Token::MOD:
313    case Token::BIT_XOR:
314    case Token::SHL:
315      return false;
316      break;
317    case Token::BIT_OR:
318    case Token::BIT_AND: {
319      Literal* left = node->left()->AsLiteral();
320      Literal* right = node->right()->AsLiteral();
321      if (left != NULL && left->handle()->IsSmi()) {
322        int value = Smi::cast(*left->handle())->value();
323        if (op == Token::BIT_OR && ((value & 0xc0000000) == 0xc0000000)) {
324          // Result of bitwise or is always a negative Smi.
325          return true;
326        }
327        if (op == Token::BIT_AND && ((value & 0xc0000000) == 0)) {
328          // Result of bitwise and is always a positive Smi.
329          return true;
330        }
331      }
332      if (right != NULL && right->handle()->IsSmi()) {
333        int value = Smi::cast(*right->handle())->value();
334        if (op == Token::BIT_OR && ((value & 0xc0000000) == 0xc0000000)) {
335          // Result of bitwise or is always a negative Smi.
336          return true;
337        }
338        if (op == Token::BIT_AND && ((value & 0xc0000000) == 0)) {
339          // Result of bitwise and is always a positive Smi.
340          return true;
341        }
342      }
343      return false;
344      break;
345    }
346    case Token::SAR:
347    case Token::SHR: {
348      Literal* right = node->right()->AsLiteral();
349       if (right != NULL && right->handle()->IsSmi()) {
350        int value = Smi::cast(*right->handle())->value();
351        if ((value & 0x1F) > 1 ||
352            (op == Token::SAR && (value & 0x1F) == 1)) {
353          return true;
354        }
355       }
356       return false;
357       break;
358    }
359    default:
360      UNREACHABLE();
361      break;
362  }
363  return false;
364}
365
366
367void Expression::CopyAnalysisResultsFrom(Expression* other) {
368  bitfields_ = other->bitfields_;
369  type_ = other->type_;
370}
371
372
373bool UnaryOperation::ResultOverwriteAllowed() {
374  switch (op_) {
375    case Token::BIT_NOT:
376    case Token::SUB:
377      return true;
378    default:
379      return false;
380  }
381}
382
383
384bool BinaryOperation::ResultOverwriteAllowed() {
385  switch (op_) {
386    case Token::COMMA:
387    case Token::OR:
388    case Token::AND:
389      return false;
390    case Token::BIT_OR:
391    case Token::BIT_XOR:
392    case Token::BIT_AND:
393    case Token::SHL:
394    case Token::SAR:
395    case Token::SHR:
396    case Token::ADD:
397    case Token::SUB:
398    case Token::MUL:
399    case Token::DIV:
400    case Token::MOD:
401      return true;
402    default:
403      UNREACHABLE();
404  }
405  return false;
406}
407
408
409BinaryOperation::BinaryOperation(Assignment* assignment) {
410  ASSERT(assignment->is_compound());
411  op_ = assignment->binary_op();
412  left_ = assignment->target();
413  right_ = assignment->value();
414  pos_ = assignment->position();
415  CopyAnalysisResultsFrom(assignment);
416}
417
418
419// ----------------------------------------------------------------------------
420// Inlining support
421
422bool Block::IsInlineable() const {
423  const int count = statements_.length();
424  for (int i = 0; i < count; ++i) {
425    if (!statements_[i]->IsInlineable()) return false;
426  }
427  return true;
428}
429
430
431bool ExpressionStatement::IsInlineable() const {
432  return expression()->IsInlineable();
433}
434
435
436bool IfStatement::IsInlineable() const {
437  return condition()->IsInlineable() && then_statement()->IsInlineable() &&
438      else_statement()->IsInlineable();
439}
440
441
442bool ReturnStatement::IsInlineable() const {
443  return expression()->IsInlineable();
444}
445
446
447bool Conditional::IsInlineable() const {
448  return condition()->IsInlineable() && then_expression()->IsInlineable() &&
449      else_expression()->IsInlineable();
450}
451
452
453bool VariableProxy::IsInlineable() const {
454  return var()->is_global() || var()->IsStackAllocated();
455}
456
457
458bool Assignment::IsInlineable() const {
459  return target()->IsInlineable() && value()->IsInlineable();
460}
461
462
463bool Property::IsInlineable() const {
464  return obj()->IsInlineable() && key()->IsInlineable();
465}
466
467
468bool Call::IsInlineable() const {
469  if (!expression()->IsInlineable()) return false;
470  const int count = arguments()->length();
471  for (int i = 0; i < count; ++i) {
472    if (!arguments()->at(i)->IsInlineable()) return false;
473  }
474  return true;
475}
476
477
478bool CallNew::IsInlineable() const {
479  if (!expression()->IsInlineable()) return false;
480  const int count = arguments()->length();
481  for (int i = 0; i < count; ++i) {
482    if (!arguments()->at(i)->IsInlineable()) return false;
483  }
484  return true;
485}
486
487
488bool CallRuntime::IsInlineable() const {
489  const int count = arguments()->length();
490  for (int i = 0; i < count; ++i) {
491    if (!arguments()->at(i)->IsInlineable()) return false;
492  }
493  return true;
494}
495
496
497bool UnaryOperation::IsInlineable() const {
498  return expression()->IsInlineable();
499}
500
501
502bool BinaryOperation::IsInlineable() const {
503  return left()->IsInlineable() && right()->IsInlineable();
504}
505
506
507bool CompareOperation::IsInlineable() const {
508  return left()->IsInlineable() && right()->IsInlineable();
509}
510
511
512bool CompareToNull::IsInlineable() const {
513  return expression()->IsInlineable();
514}
515
516
517bool CountOperation::IsInlineable() const {
518  return expression()->IsInlineable();
519}
520
521
522// ----------------------------------------------------------------------------
523// Recording of type feedback
524
525void Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
526  // Record type feedback from the oracle in the AST.
527  is_monomorphic_ = oracle->LoadIsMonomorphic(this);
528  if (key()->IsPropertyName()) {
529    if (oracle->LoadIsBuiltin(this, Builtins::LoadIC_ArrayLength)) {
530      is_array_length_ = true;
531    } else if (oracle->LoadIsBuiltin(this, Builtins::LoadIC_StringLength)) {
532      is_string_length_ = true;
533    } else if (oracle->LoadIsBuiltin(this,
534                                     Builtins::LoadIC_FunctionPrototype)) {
535      is_function_prototype_ = true;
536    } else {
537      Literal* lit_key = key()->AsLiteral();
538      ASSERT(lit_key != NULL && lit_key->handle()->IsString());
539      Handle<String> name = Handle<String>::cast(lit_key->handle());
540      ZoneMapList* types = oracle->LoadReceiverTypes(this, name);
541      receiver_types_ = types;
542    }
543  } else if (is_monomorphic_) {
544    monomorphic_receiver_type_ = oracle->LoadMonomorphicReceiverType(this);
545  }
546}
547
548
549void Assignment::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
550  Property* prop = target()->AsProperty();
551  ASSERT(prop != NULL);
552  is_monomorphic_ = oracle->StoreIsMonomorphic(this);
553  if (prop->key()->IsPropertyName()) {
554    Literal* lit_key = prop->key()->AsLiteral();
555    ASSERT(lit_key != NULL && lit_key->handle()->IsString());
556    Handle<String> name = Handle<String>::cast(lit_key->handle());
557    ZoneMapList* types = oracle->StoreReceiverTypes(this, name);
558    receiver_types_ = types;
559  } else if (is_monomorphic_) {
560    // Record receiver type for monomorphic keyed loads.
561    monomorphic_receiver_type_ = oracle->StoreMonomorphicReceiverType(this);
562  }
563}
564
565
566void CaseClause::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
567  TypeInfo info = oracle->SwitchType(this);
568  if (info.IsSmi()) {
569    compare_type_ = SMI_ONLY;
570  } else if (info.IsNonPrimitive()) {
571    compare_type_ = OBJECT_ONLY;
572  } else {
573    ASSERT(compare_type_ == NONE);
574  }
575}
576
577
578static bool CanCallWithoutIC(Handle<JSFunction> target, int arity) {
579  SharedFunctionInfo* info = target->shared();
580  // If the number of formal parameters of the target function does
581  // not match the number of arguments we're passing, we don't want to
582  // deal with it. Otherwise, we can call it directly.
583  return !target->NeedsArgumentsAdaption() ||
584      info->formal_parameter_count() == arity;
585}
586
587
588bool Call::ComputeTarget(Handle<Map> type, Handle<String> name) {
589  if (check_type_ == RECEIVER_MAP_CHECK) {
590    // For primitive checks the holder is set up to point to the
591    // corresponding prototype object, i.e. one step of the algorithm
592    // below has been already performed.
593    // For non-primitive checks we clear it to allow computing targets
594    // for polymorphic calls.
595    holder_ = Handle<JSObject>::null();
596  }
597  while (true) {
598    LookupResult lookup;
599    type->LookupInDescriptors(NULL, *name, &lookup);
600    // If the function wasn't found directly in the map, we start
601    // looking upwards through the prototype chain.
602    if (!lookup.IsFound() && type->prototype()->IsJSObject()) {
603      holder_ = Handle<JSObject>(JSObject::cast(type->prototype()));
604      type = Handle<Map>(holder()->map());
605    } else if (lookup.IsProperty() && lookup.type() == CONSTANT_FUNCTION) {
606      target_ = Handle<JSFunction>(lookup.GetConstantFunctionFromMap(*type));
607      return CanCallWithoutIC(target_, arguments()->length());
608    } else {
609      return false;
610    }
611  }
612}
613
614
615bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
616                               Handle<String> name) {
617  target_ = Handle<JSFunction>::null();
618  cell_ = Handle<JSGlobalPropertyCell>::null();
619  LookupResult lookup;
620  global->Lookup(*name, &lookup);
621  if (lookup.IsProperty() &&
622      lookup.type() == NORMAL &&
623      lookup.holder() == *global) {
624    cell_ = Handle<JSGlobalPropertyCell>(global->GetPropertyCell(&lookup));
625    if (cell_->value()->IsJSFunction()) {
626      Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
627      // If the function is in new space we assume it's more likely to
628      // change and thus prefer the general IC code.
629      if (!Heap::InNewSpace(*candidate) &&
630          CanCallWithoutIC(candidate, arguments()->length())) {
631        target_ = candidate;
632        return true;
633      }
634    }
635  }
636  return false;
637}
638
639
640void Call::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
641  Property* property = expression()->AsProperty();
642  ASSERT(property != NULL);
643  // Specialize for the receiver types seen at runtime.
644  Literal* key = property->key()->AsLiteral();
645  ASSERT(key != NULL && key->handle()->IsString());
646  Handle<String> name = Handle<String>::cast(key->handle());
647  receiver_types_ = oracle->CallReceiverTypes(this, name);
648#ifdef DEBUG
649  if (FLAG_enable_slow_asserts) {
650    if (receiver_types_ != NULL) {
651      int length = receiver_types_->length();
652      for (int i = 0; i < length; i++) {
653        Handle<Map> map = receiver_types_->at(i);
654        ASSERT(!map.is_null() && *map != NULL);
655      }
656    }
657  }
658#endif
659  is_monomorphic_ = oracle->CallIsMonomorphic(this);
660  check_type_ = oracle->GetCallCheckType(this);
661  if (is_monomorphic_) {
662    Handle<Map> map;
663    if (receiver_types_ != NULL && receiver_types_->length() > 0) {
664      ASSERT(check_type_ == RECEIVER_MAP_CHECK);
665      map = receiver_types_->at(0);
666    } else {
667      ASSERT(check_type_ != RECEIVER_MAP_CHECK);
668      holder_ = Handle<JSObject>(
669          oracle->GetPrototypeForPrimitiveCheck(check_type_));
670      map = Handle<Map>(holder_->map());
671    }
672    is_monomorphic_ = ComputeTarget(map, name);
673  }
674}
675
676
677void CompareOperation::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
678  TypeInfo info = oracle->CompareType(this);
679  if (info.IsSmi()) {
680    compare_type_ = SMI_ONLY;
681  } else if (info.IsNonPrimitive()) {
682    compare_type_ = OBJECT_ONLY;
683  } else {
684    ASSERT(compare_type_ == NONE);
685  }
686}
687
688
689// ----------------------------------------------------------------------------
690// Implementation of AstVisitor
691
692bool AstVisitor::CheckStackOverflow() {
693  if (stack_overflow_) return true;
694  StackLimitCheck check;
695  if (!check.HasOverflowed()) return false;
696  return (stack_overflow_ = true);
697}
698
699
700void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
701  for (int i = 0; i < declarations->length(); i++) {
702    Visit(declarations->at(i));
703  }
704}
705
706
707void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
708  for (int i = 0; i < statements->length(); i++) {
709    Visit(statements->at(i));
710  }
711}
712
713
714void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
715  for (int i = 0; i < expressions->length(); i++) {
716    // The variable statement visiting code may pass NULL expressions
717    // to this code. Maybe this should be handled by introducing an
718    // undefined expression or literal?  Revisit this code if this
719    // changes
720    Expression* expression = expressions->at(i);
721    if (expression != NULL) Visit(expression);
722  }
723}
724
725
726// ----------------------------------------------------------------------------
727// Regular expressions
728
729#define MAKE_ACCEPT(Name)                                            \
730  void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
731    return visitor->Visit##Name(this, data);                         \
732  }
733FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
734#undef MAKE_ACCEPT
735
736#define MAKE_TYPE_CASE(Name)                                         \
737  RegExp##Name* RegExpTree::As##Name() {                             \
738    return NULL;                                                     \
739  }                                                                  \
740  bool RegExpTree::Is##Name() { return false; }
741FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
742#undef MAKE_TYPE_CASE
743
744#define MAKE_TYPE_CASE(Name)                                        \
745  RegExp##Name* RegExp##Name::As##Name() {                          \
746    return this;                                                    \
747  }                                                                 \
748  bool RegExp##Name::Is##Name() { return true; }
749FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
750#undef MAKE_TYPE_CASE
751
752RegExpEmpty RegExpEmpty::kInstance;
753
754
755static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
756  Interval result = Interval::Empty();
757  for (int i = 0; i < children->length(); i++)
758    result = result.Union(children->at(i)->CaptureRegisters());
759  return result;
760}
761
762
763Interval RegExpAlternative::CaptureRegisters() {
764  return ListCaptureRegisters(nodes());
765}
766
767
768Interval RegExpDisjunction::CaptureRegisters() {
769  return ListCaptureRegisters(alternatives());
770}
771
772
773Interval RegExpLookahead::CaptureRegisters() {
774  return body()->CaptureRegisters();
775}
776
777
778Interval RegExpCapture::CaptureRegisters() {
779  Interval self(StartRegister(index()), EndRegister(index()));
780  return self.Union(body()->CaptureRegisters());
781}
782
783
784Interval RegExpQuantifier::CaptureRegisters() {
785  return body()->CaptureRegisters();
786}
787
788
789bool RegExpAssertion::IsAnchoredAtStart() {
790  return type() == RegExpAssertion::START_OF_INPUT;
791}
792
793
794bool RegExpAssertion::IsAnchoredAtEnd() {
795  return type() == RegExpAssertion::END_OF_INPUT;
796}
797
798
799bool RegExpAlternative::IsAnchoredAtStart() {
800  ZoneList<RegExpTree*>* nodes = this->nodes();
801  for (int i = 0; i < nodes->length(); i++) {
802    RegExpTree* node = nodes->at(i);
803    if (node->IsAnchoredAtStart()) { return true; }
804    if (node->max_match() > 0) { return false; }
805  }
806  return false;
807}
808
809
810bool RegExpAlternative::IsAnchoredAtEnd() {
811  ZoneList<RegExpTree*>* nodes = this->nodes();
812  for (int i = nodes->length() - 1; i >= 0; i--) {
813    RegExpTree* node = nodes->at(i);
814    if (node->IsAnchoredAtEnd()) { return true; }
815    if (node->max_match() > 0) { return false; }
816  }
817  return false;
818}
819
820
821bool RegExpDisjunction::IsAnchoredAtStart() {
822  ZoneList<RegExpTree*>* alternatives = this->alternatives();
823  for (int i = 0; i < alternatives->length(); i++) {
824    if (!alternatives->at(i)->IsAnchoredAtStart())
825      return false;
826  }
827  return true;
828}
829
830
831bool RegExpDisjunction::IsAnchoredAtEnd() {
832  ZoneList<RegExpTree*>* alternatives = this->alternatives();
833  for (int i = 0; i < alternatives->length(); i++) {
834    if (!alternatives->at(i)->IsAnchoredAtEnd())
835      return false;
836  }
837  return true;
838}
839
840
841bool RegExpLookahead::IsAnchoredAtStart() {
842  return is_positive() && body()->IsAnchoredAtStart();
843}
844
845
846bool RegExpCapture::IsAnchoredAtStart() {
847  return body()->IsAnchoredAtStart();
848}
849
850
851bool RegExpCapture::IsAnchoredAtEnd() {
852  return body()->IsAnchoredAtEnd();
853}
854
855
856// Convert regular expression trees to a simple sexp representation.
857// This representation should be different from the input grammar
858// in as many cases as possible, to make it more difficult for incorrect
859// parses to look as correct ones which is likely if the input and
860// output formats are alike.
861class RegExpUnparser: public RegExpVisitor {
862 public:
863  RegExpUnparser();
864  void VisitCharacterRange(CharacterRange that);
865  SmartPointer<const char> ToString() { return stream_.ToCString(); }
866#define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data);
867  FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
868#undef MAKE_CASE
869 private:
870  StringStream* stream() { return &stream_; }
871  HeapStringAllocator alloc_;
872  StringStream stream_;
873};
874
875
876RegExpUnparser::RegExpUnparser() : stream_(&alloc_) {
877}
878
879
880void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
881  stream()->Add("(|");
882  for (int i = 0; i <  that->alternatives()->length(); i++) {
883    stream()->Add(" ");
884    that->alternatives()->at(i)->Accept(this, data);
885  }
886  stream()->Add(")");
887  return NULL;
888}
889
890
891void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
892  stream()->Add("(:");
893  for (int i = 0; i <  that->nodes()->length(); i++) {
894    stream()->Add(" ");
895    that->nodes()->at(i)->Accept(this, data);
896  }
897  stream()->Add(")");
898  return NULL;
899}
900
901
902void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
903  stream()->Add("%k", that.from());
904  if (!that.IsSingleton()) {
905    stream()->Add("-%k", that.to());
906  }
907}
908
909
910
911void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
912                                          void* data) {
913  if (that->is_negated())
914    stream()->Add("^");
915  stream()->Add("[");
916  for (int i = 0; i < that->ranges()->length(); i++) {
917    if (i > 0) stream()->Add(" ");
918    VisitCharacterRange(that->ranges()->at(i));
919  }
920  stream()->Add("]");
921  return NULL;
922}
923
924
925void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
926  switch (that->type()) {
927    case RegExpAssertion::START_OF_INPUT:
928      stream()->Add("@^i");
929      break;
930    case RegExpAssertion::END_OF_INPUT:
931      stream()->Add("@$i");
932      break;
933    case RegExpAssertion::START_OF_LINE:
934      stream()->Add("@^l");
935      break;
936    case RegExpAssertion::END_OF_LINE:
937      stream()->Add("@$l");
938       break;
939    case RegExpAssertion::BOUNDARY:
940      stream()->Add("@b");
941      break;
942    case RegExpAssertion::NON_BOUNDARY:
943      stream()->Add("@B");
944      break;
945  }
946  return NULL;
947}
948
949
950void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
951  stream()->Add("'");
952  Vector<const uc16> chardata = that->data();
953  for (int i = 0; i < chardata.length(); i++) {
954    stream()->Add("%k", chardata[i]);
955  }
956  stream()->Add("'");
957  return NULL;
958}
959
960
961void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
962  if (that->elements()->length() == 1) {
963    that->elements()->at(0).data.u_atom->Accept(this, data);
964  } else {
965    stream()->Add("(!");
966    for (int i = 0; i < that->elements()->length(); i++) {
967      stream()->Add(" ");
968      that->elements()->at(i).data.u_atom->Accept(this, data);
969    }
970    stream()->Add(")");
971  }
972  return NULL;
973}
974
975
976void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
977  stream()->Add("(# %i ", that->min());
978  if (that->max() == RegExpTree::kInfinity) {
979    stream()->Add("- ");
980  } else {
981    stream()->Add("%i ", that->max());
982  }
983  stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
984  that->body()->Accept(this, data);
985  stream()->Add(")");
986  return NULL;
987}
988
989
990void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
991  stream()->Add("(^ ");
992  that->body()->Accept(this, data);
993  stream()->Add(")");
994  return NULL;
995}
996
997
998void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
999  stream()->Add("(-> ");
1000  stream()->Add(that->is_positive() ? "+ " : "- ");
1001  that->body()->Accept(this, data);
1002  stream()->Add(")");
1003  return NULL;
1004}
1005
1006
1007void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
1008                                         void* data) {
1009  stream()->Add("(<- %i)", that->index());
1010  return NULL;
1011}
1012
1013
1014void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
1015  stream()->Put('%');
1016  return NULL;
1017}
1018
1019
1020SmartPointer<const char> RegExpTree::ToString() {
1021  RegExpUnparser unparser;
1022  Accept(&unparser, NULL);
1023  return unparser.ToString();
1024}
1025
1026
1027RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
1028    : alternatives_(alternatives) {
1029  ASSERT(alternatives->length() > 1);
1030  RegExpTree* first_alternative = alternatives->at(0);
1031  min_match_ = first_alternative->min_match();
1032  max_match_ = first_alternative->max_match();
1033  for (int i = 1; i < alternatives->length(); i++) {
1034    RegExpTree* alternative = alternatives->at(i);
1035    min_match_ = Min(min_match_, alternative->min_match());
1036    max_match_ = Max(max_match_, alternative->max_match());
1037  }
1038}
1039
1040
1041RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
1042    : nodes_(nodes) {
1043  ASSERT(nodes->length() > 1);
1044  min_match_ = 0;
1045  max_match_ = 0;
1046  for (int i = 0; i < nodes->length(); i++) {
1047    RegExpTree* node = nodes->at(i);
1048    min_match_ += node->min_match();
1049    int node_max_match = node->max_match();
1050    if (kInfinity - max_match_ < node_max_match) {
1051      max_match_ = kInfinity;
1052    } else {
1053      max_match_ += node->max_match();
1054    }
1055  }
1056}
1057
1058
1059CaseClause::CaseClause(Expression* label,
1060                       ZoneList<Statement*>* statements,
1061                       int pos)
1062    : label_(label),
1063      statements_(statements),
1064      position_(pos),
1065      compare_type_(NONE) {}
1066
1067} }  // namespace v8::internal
1068