ast.cc revision 9ac36c9faca11611ada13b4054edbaa0738661d0 
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 "parser.h"
32#include "scopes.h"
33#include "string-stream.h"
34#include "ast-inl.h"
35#include "jump-target-inl.h"
36
37namespace v8 {
38namespace internal {
39
40
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
51#define DECL_ACCEPT(type)                                       \
52  void type::Accept(AstVisitor* v) { v->Visit##type(this); }
53AST_NODE_LIST(DECL_ACCEPT)
54#undef DECL_ACCEPT
55
56
57// ----------------------------------------------------------------------------
58// Implementation of other node functionality.
59
60Assignment* ExpressionStatement::StatementAsSimpleAssignment() {
61  return (expression()->AsAssignment() != NULL &&
62          !expression()->AsAssignment()->is_compound())
63      ? expression()->AsAssignment()
64      : NULL;
65}
66
67
68CountOperation* ExpressionStatement::StatementAsCountOperation() {
69  return expression()->AsCountOperation();
70}
71
72
73VariableProxy::VariableProxy(Handle<String> name,
74                             bool is_this,
75                             bool inside_with)
76  : name_(name),
77    var_(NULL),
78    is_this_(is_this),
79    inside_with_(inside_with),
80    is_trivial_(false) {
81  // names must be canonicalized for fast equality checks
82  ASSERT(name->IsSymbol());
83}
84
85
86VariableProxy::VariableProxy(bool is_this)
87  : var_(NULL),
88    is_this_(is_this),
89    inside_with_(false),
90    is_trivial_(false) {
91}
92
93
94void VariableProxy::BindTo(Variable* var) {
95  ASSERT(var_ == NULL);  // must be bound only once
96  ASSERT(var != NULL);  // must bind
97  ASSERT((is_this() && var->is_this()) || name_.is_identical_to(var->name()));
98  // Ideally CONST-ness should match. However, this is very hard to achieve
99  // because we don't know the exact semantics of conflicting (const and
100  // non-const) multiple variable declarations, const vars introduced via
101  // eval() etc.  Const-ness and variable declarations are a complete mess
102  // in JS. Sigh...
103  var_ = var;
104  var->set_is_used(true);
105}
106
107
108Token::Value Assignment::binary_op() const {
109  switch (op_) {
110    case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
111    case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
112    case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
113    case Token::ASSIGN_SHL: return Token::SHL;
114    case Token::ASSIGN_SAR: return Token::SAR;
115    case Token::ASSIGN_SHR: return Token::SHR;
116    case Token::ASSIGN_ADD: return Token::ADD;
117    case Token::ASSIGN_SUB: return Token::SUB;
118    case Token::ASSIGN_MUL: return Token::MUL;
119    case Token::ASSIGN_DIV: return Token::DIV;
120    case Token::ASSIGN_MOD: return Token::MOD;
121    default: UNREACHABLE();
122  }
123  return Token::ILLEGAL;
124}
125
126
127bool FunctionLiteral::AllowsLazyCompilation() {
128  return scope()->AllowsLazyCompilation();
129}
130
131
132ObjectLiteral::Property::Property(Literal* key, Expression* value) {
133  key_ = key;
134  value_ = value;
135  Object* k = *key->handle();
136  if (k->IsSymbol() && Heap::Proto_symbol()->Equals(String::cast(k))) {
137    kind_ = PROTOTYPE;
138  } else if (value_->AsMaterializedLiteral() != NULL) {
139    kind_ = MATERIALIZED_LITERAL;
140  } else if (value_->AsLiteral() != NULL) {
141    kind_ = CONSTANT;
142  } else {
143    kind_ = COMPUTED;
144  }
145}
146
147
148ObjectLiteral::Property::Property(bool is_getter, FunctionLiteral* value) {
149  key_ = new Literal(value->name());
150  value_ = value;
151  kind_ = is_getter ? GETTER : SETTER;
152}
153
154
155bool ObjectLiteral::Property::IsCompileTimeValue() {
156  return kind_ == CONSTANT ||
157      (kind_ == MATERIALIZED_LITERAL &&
158       CompileTimeValue::IsCompileTimeValue(value_));
159}
160
161
162void TargetCollector::AddTarget(BreakTarget* target) {
163  // Add the label to the collector, but discard duplicates.
164  int length = targets_->length();
165  for (int i = 0; i < length; i++) {
166    if (targets_->at(i) == target) return;
167  }
168  targets_->Add(target);
169}
170
171
172bool Expression::GuaranteedSmiResult() {
173  BinaryOperation* node = AsBinaryOperation();
174  if (node == NULL) return false;
175  Token::Value op = node->op();
176  switch (op) {
177    case Token::COMMA:
178    case Token::OR:
179    case Token::AND:
180    case Token::ADD:
181    case Token::SUB:
182    case Token::MUL:
183    case Token::DIV:
184    case Token::MOD:
185    case Token::BIT_XOR:
186    case Token::SHL:
187      return false;
188      break;
189    case Token::BIT_OR:
190    case Token::BIT_AND: {
191      Literal* left = node->left()->AsLiteral();
192      Literal* right = node->right()->AsLiteral();
193      if (left != NULL && left->handle()->IsSmi()) {
194        int value = Smi::cast(*left->handle())->value();
195        if (op == Token::BIT_OR && ((value & 0xc0000000) == 0xc0000000)) {
196          // Result of bitwise or is always a negative Smi.
197          return true;
198        }
199        if (op == Token::BIT_AND && ((value & 0xc0000000) == 0)) {
200          // Result of bitwise and is always a positive Smi.
201          return true;
202        }
203      }
204      if (right != NULL && right->handle()->IsSmi()) {
205        int value = Smi::cast(*right->handle())->value();
206        if (op == Token::BIT_OR && ((value & 0xc0000000) == 0xc0000000)) {
207          // Result of bitwise or is always a negative Smi.
208          return true;
209        }
210        if (op == Token::BIT_AND && ((value & 0xc0000000) == 0)) {
211          // Result of bitwise and is always a positive Smi.
212          return true;
213        }
214      }
215      return false;
216      break;
217    }
218    case Token::SAR:
219    case Token::SHR: {
220      Literal* right = node->right()->AsLiteral();
221       if (right != NULL && right->handle()->IsSmi()) {
222        int value = Smi::cast(*right->handle())->value();
223        if ((value & 0x1F) > 1 ||
224            (op == Token::SAR && (value & 0x1F) == 1)) {
225          return true;
226        }
227       }
228       return false;
229       break;
230    }
231    default:
232      UNREACHABLE();
233      break;
234  }
235  return false;
236}
237
238
239void Expression::CopyAnalysisResultsFrom(Expression* other) {
240  bitfields_ = other->bitfields_;
241  type_ = other->type_;
242}
243
244
245bool UnaryOperation::ResultOverwriteAllowed() {
246  switch (op_) {
247    case Token::BIT_NOT:
248    case Token::SUB:
249      return true;
250    default:
251      return false;
252  }
253}
254
255
256bool BinaryOperation::ResultOverwriteAllowed() {
257  switch (op_) {
258    case Token::COMMA:
259    case Token::OR:
260    case Token::AND:
261      return false;
262    case Token::BIT_OR:
263    case Token::BIT_XOR:
264    case Token::BIT_AND:
265    case Token::SHL:
266    case Token::SAR:
267    case Token::SHR:
268    case Token::ADD:
269    case Token::SUB:
270    case Token::MUL:
271    case Token::DIV:
272    case Token::MOD:
273      return true;
274    default:
275      UNREACHABLE();
276  }
277  return false;
278}
279
280
281BinaryOperation::BinaryOperation(Assignment* assignment) {
282  ASSERT(assignment->is_compound());
283  op_ = assignment->binary_op();
284  left_ = assignment->target();
285  right_ = assignment->value();
286  pos_ = assignment->position();
287  CopyAnalysisResultsFrom(assignment);
288}
289
290
291// ----------------------------------------------------------------------------
292// Implementation of AstVisitor
293
294bool AstVisitor::CheckStackOverflow() {
295  if (stack_overflow_) return true;
296  StackLimitCheck check;
297  if (!check.HasOverflowed()) return false;
298  return (stack_overflow_ = true);
299}
300
301
302void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
303  for (int i = 0; i < declarations->length(); i++) {
304    Visit(declarations->at(i));
305  }
306}
307
308
309void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
310  for (int i = 0; i < statements->length(); i++) {
311    Visit(statements->at(i));
312  }
313}
314
315
316void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
317  for (int i = 0; i < expressions->length(); i++) {
318    // The variable statement visiting code may pass NULL expressions
319    // to this code. Maybe this should be handled by introducing an
320    // undefined expression or literal?  Revisit this code if this
321    // changes
322    Expression* expression = expressions->at(i);
323    if (expression != NULL) Visit(expression);
324  }
325}
326
327
328// ----------------------------------------------------------------------------
329// Regular expressions
330
331#define MAKE_ACCEPT(Name)                                            \
332  void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
333    return visitor->Visit##Name(this, data);                         \
334  }
335FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
336#undef MAKE_ACCEPT
337
338#define MAKE_TYPE_CASE(Name)                                         \
339  RegExp##Name* RegExpTree::As##Name() {                             \
340    return NULL;                                                     \
341  }                                                                  \
342  bool RegExpTree::Is##Name() { return false; }
343FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
344#undef MAKE_TYPE_CASE
345
346#define MAKE_TYPE_CASE(Name)                                        \
347  RegExp##Name* RegExp##Name::As##Name() {                          \
348    return this;                                                    \
349  }                                                                 \
350  bool RegExp##Name::Is##Name() { return true; }
351FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
352#undef MAKE_TYPE_CASE
353
354RegExpEmpty RegExpEmpty::kInstance;
355
356
357static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
358  Interval result = Interval::Empty();
359  for (int i = 0; i < children->length(); i++)
360    result = result.Union(children->at(i)->CaptureRegisters());
361  return result;
362}
363
364
365Interval RegExpAlternative::CaptureRegisters() {
366  return ListCaptureRegisters(nodes());
367}
368
369
370Interval RegExpDisjunction::CaptureRegisters() {
371  return ListCaptureRegisters(alternatives());
372}
373
374
375Interval RegExpLookahead::CaptureRegisters() {
376  return body()->CaptureRegisters();
377}
378
379
380Interval RegExpCapture::CaptureRegisters() {
381  Interval self(StartRegister(index()), EndRegister(index()));
382  return self.Union(body()->CaptureRegisters());
383}
384
385
386Interval RegExpQuantifier::CaptureRegisters() {
387  return body()->CaptureRegisters();
388}
389
390
391bool RegExpAssertion::IsAnchored() {
392  return type() == RegExpAssertion::START_OF_INPUT;
393}
394
395
396bool RegExpAlternative::IsAnchored() {
397  ZoneList<RegExpTree*>* nodes = this->nodes();
398  for (int i = 0; i < nodes->length(); i++) {
399    RegExpTree* node = nodes->at(i);
400    if (node->IsAnchored()) { return true; }
401    if (node->max_match() > 0) { return false; }
402  }
403  return false;
404}
405
406
407bool RegExpDisjunction::IsAnchored() {
408  ZoneList<RegExpTree*>* alternatives = this->alternatives();
409  for (int i = 0; i < alternatives->length(); i++) {
410    if (!alternatives->at(i)->IsAnchored())
411      return false;
412  }
413  return true;
414}
415
416
417bool RegExpLookahead::IsAnchored() {
418  return is_positive() && body()->IsAnchored();
419}
420
421
422bool RegExpCapture::IsAnchored() {
423  return body()->IsAnchored();
424}
425
426
427// Convert regular expression trees to a simple sexp representation.
428// This representation should be different from the input grammar
429// in as many cases as possible, to make it more difficult for incorrect
430// parses to look as correct ones which is likely if the input and
431// output formats are alike.
432class RegExpUnparser: public RegExpVisitor {
433 public:
434  RegExpUnparser();
435  void VisitCharacterRange(CharacterRange that);
436  SmartPointer<const char> ToString() { return stream_.ToCString(); }
437#define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data);
438  FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
439#undef MAKE_CASE
440 private:
441  StringStream* stream() { return &stream_; }
442  HeapStringAllocator alloc_;
443  StringStream stream_;
444};
445
446
447RegExpUnparser::RegExpUnparser() : stream_(&alloc_) {
448}
449
450
451void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
452  stream()->Add("(|");
453  for (int i = 0; i <  that->alternatives()->length(); i++) {
454    stream()->Add(" ");
455    that->alternatives()->at(i)->Accept(this, data);
456  }
457  stream()->Add(")");
458  return NULL;
459}
460
461
462void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
463  stream()->Add("(:");
464  for (int i = 0; i <  that->nodes()->length(); i++) {
465    stream()->Add(" ");
466    that->nodes()->at(i)->Accept(this, data);
467  }
468  stream()->Add(")");
469  return NULL;
470}
471
472
473void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
474  stream()->Add("%k", that.from());
475  if (!that.IsSingleton()) {
476    stream()->Add("-%k", that.to());
477  }
478}
479
480
481
482void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
483                                          void* data) {
484  if (that->is_negated())
485    stream()->Add("^");
486  stream()->Add("[");
487  for (int i = 0; i < that->ranges()->length(); i++) {
488    if (i > 0) stream()->Add(" ");
489    VisitCharacterRange(that->ranges()->at(i));
490  }
491  stream()->Add("]");
492  return NULL;
493}
494
495
496void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
497  switch (that->type()) {
498    case RegExpAssertion::START_OF_INPUT:
499      stream()->Add("@^i");
500      break;
501    case RegExpAssertion::END_OF_INPUT:
502      stream()->Add("@$i");
503      break;
504    case RegExpAssertion::START_OF_LINE:
505      stream()->Add("@^l");
506      break;
507    case RegExpAssertion::END_OF_LINE:
508      stream()->Add("@$l");
509       break;
510    case RegExpAssertion::BOUNDARY:
511      stream()->Add("@b");
512      break;
513    case RegExpAssertion::NON_BOUNDARY:
514      stream()->Add("@B");
515      break;
516  }
517  return NULL;
518}
519
520
521void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
522  stream()->Add("'");
523  Vector<const uc16> chardata = that->data();
524  for (int i = 0; i < chardata.length(); i++) {
525    stream()->Add("%k", chardata[i]);
526  }
527  stream()->Add("'");
528  return NULL;
529}
530
531
532void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
533  if (that->elements()->length() == 1) {
534    that->elements()->at(0).data.u_atom->Accept(this, data);
535  } else {
536    stream()->Add("(!");
537    for (int i = 0; i < that->elements()->length(); i++) {
538      stream()->Add(" ");
539      that->elements()->at(i).data.u_atom->Accept(this, data);
540    }
541    stream()->Add(")");
542  }
543  return NULL;
544}
545
546
547void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
548  stream()->Add("(# %i ", that->min());
549  if (that->max() == RegExpTree::kInfinity) {
550    stream()->Add("- ");
551  } else {
552    stream()->Add("%i ", that->max());
553  }
554  stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
555  that->body()->Accept(this, data);
556  stream()->Add(")");
557  return NULL;
558}
559
560
561void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
562  stream()->Add("(^ ");
563  that->body()->Accept(this, data);
564  stream()->Add(")");
565  return NULL;
566}
567
568
569void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
570  stream()->Add("(-> ");
571  stream()->Add(that->is_positive() ? "+ " : "- ");
572  that->body()->Accept(this, data);
573  stream()->Add(")");
574  return NULL;
575}
576
577
578void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
579                                         void* data) {
580  stream()->Add("(<- %i)", that->index());
581  return NULL;
582}
583
584
585void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
586  stream()->Put('%');
587  return NULL;
588}
589
590
591SmartPointer<const char> RegExpTree::ToString() {
592  RegExpUnparser unparser;
593  Accept(&unparser, NULL);
594  return unparser.ToString();
595}
596
597
598RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
599    : alternatives_(alternatives) {
600  ASSERT(alternatives->length() > 1);
601  RegExpTree* first_alternative = alternatives->at(0);
602  min_match_ = first_alternative->min_match();
603  max_match_ = first_alternative->max_match();
604  for (int i = 1; i < alternatives->length(); i++) {
605    RegExpTree* alternative = alternatives->at(i);
606    min_match_ = Min(min_match_, alternative->min_match());
607    max_match_ = Max(max_match_, alternative->max_match());
608  }
609}
610
611
612RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
613    : nodes_(nodes) {
614  ASSERT(nodes->length() > 1);
615  min_match_ = 0;
616  max_match_ = 0;
617  for (int i = 0; i < nodes->length(); i++) {
618    RegExpTree* node = nodes->at(i);
619    min_match_ += node->min_match();
620    int node_max_match = node->max_match();
621    if (kInfinity - max_match_ < node_max_match) {
622      max_match_ = kInfinity;
623    } else {
624      max_match_ += node->max_match();
625    }
626  }
627}
628
629
630WhileStatement::WhileStatement(ZoneStringList* labels)
631    : IterationStatement(labels),
632      cond_(NULL),
633      may_have_function_literal_(true) {
634}
635
636
637CaseClause::CaseClause(Expression* label, ZoneList<Statement*>* statements)
638    : label_(label), statements_(statements) {
639}
640
641} }  // namespace v8::internal
642