| // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following |
| // disclaimer in the documentation and/or other materials provided |
| // with the distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived |
| // from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #include "v8.h" |
| |
| #include "ast.h" |
| #include "scopes.h" |
| #include "string-stream.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| |
| VariableProxySentinel VariableProxySentinel::this_proxy_(true); |
| VariableProxySentinel VariableProxySentinel::identifier_proxy_(false); |
| ValidLeftHandSideSentinel ValidLeftHandSideSentinel::instance_; |
| Property Property::this_property_(VariableProxySentinel::this_proxy(), NULL, 0); |
| Call Call::sentinel_(NULL, NULL, 0); |
| CallEval CallEval::sentinel_(NULL, NULL, 0); |
| |
| |
| // ---------------------------------------------------------------------------- |
| // All the Accept member functions for each syntax tree node type. |
| |
| #define DECL_ACCEPT(type) \ |
| void type::Accept(AstVisitor* v) { \ |
| if (v->CheckStackOverflow()) return; \ |
| v->Visit##type(this); \ |
| } |
| AST_NODE_LIST(DECL_ACCEPT) |
| #undef DECL_ACCEPT |
| |
| |
| // ---------------------------------------------------------------------------- |
| // Implementation of other node functionality. |
| |
| VariableProxy::VariableProxy(Handle<String> name, |
| bool is_this, |
| bool inside_with) |
| : name_(name), |
| var_(NULL), |
| is_this_(is_this), |
| inside_with_(inside_with) { |
| // names must be canonicalized for fast equality checks |
| ASSERT(name->IsSymbol()); |
| // at least one access, otherwise no need for a VariableProxy |
| var_uses_.RecordRead(1); |
| } |
| |
| |
| VariableProxy::VariableProxy(bool is_this) |
| : is_this_(is_this) { |
| } |
| |
| |
| void VariableProxy::BindTo(Variable* var) { |
| ASSERT(var_ == NULL); // must be bound only once |
| ASSERT(var != NULL); // must bind |
| ASSERT((is_this() && var->is_this()) || name_.is_identical_to(var->name())); |
| // Ideally CONST-ness should match. However, this is very hard to achieve |
| // because we don't know the exact semantics of conflicting (const and |
| // non-const) multiple variable declarations, const vars introduced via |
| // eval() etc. Const-ness and variable declarations are a complete mess |
| // in JS. Sigh... |
| var_ = var; |
| var->var_uses()->RecordUses(&var_uses_); |
| var->obj_uses()->RecordUses(&obj_uses_); |
| } |
| |
| |
| #ifdef DEBUG |
| |
| const char* LoopStatement::OperatorString() const { |
| switch (type()) { |
| case DO_LOOP: return "DO"; |
| case FOR_LOOP: return "FOR"; |
| case WHILE_LOOP: return "WHILE"; |
| } |
| return NULL; |
| } |
| |
| #endif // DEBUG |
| |
| |
| Token::Value Assignment::binary_op() const { |
| switch (op_) { |
| case Token::ASSIGN_BIT_OR: return Token::BIT_OR; |
| case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR; |
| case Token::ASSIGN_BIT_AND: return Token::BIT_AND; |
| case Token::ASSIGN_SHL: return Token::SHL; |
| case Token::ASSIGN_SAR: return Token::SAR; |
| case Token::ASSIGN_SHR: return Token::SHR; |
| case Token::ASSIGN_ADD: return Token::ADD; |
| case Token::ASSIGN_SUB: return Token::SUB; |
| case Token::ASSIGN_MUL: return Token::MUL; |
| case Token::ASSIGN_DIV: return Token::DIV; |
| case Token::ASSIGN_MOD: return Token::MOD; |
| default: UNREACHABLE(); |
| } |
| return Token::ILLEGAL; |
| } |
| |
| |
| bool FunctionLiteral::AllowsLazyCompilation() { |
| return scope()->AllowsLazyCompilation(); |
| } |
| |
| |
| ObjectLiteral::Property::Property(Literal* key, Expression* value) { |
| key_ = key; |
| value_ = value; |
| Object* k = *key->handle(); |
| if (k->IsSymbol() && Heap::Proto_symbol()->Equals(String::cast(k))) { |
| kind_ = PROTOTYPE; |
| } else if (value_->AsMaterializedLiteral() != NULL) { |
| kind_ = MATERIALIZED_LITERAL; |
| } else if (value_->AsLiteral() != NULL) { |
| kind_ = CONSTANT; |
| } else { |
| kind_ = COMPUTED; |
| } |
| } |
| |
| |
| ObjectLiteral::Property::Property(bool is_getter, FunctionLiteral* value) { |
| key_ = new Literal(value->name()); |
| value_ = value; |
| kind_ = is_getter ? GETTER : SETTER; |
| } |
| |
| |
| bool ObjectLiteral::IsValidJSON() { |
| int length = properties()->length(); |
| for (int i = 0; i < length; i++) { |
| Property* prop = properties()->at(i); |
| if (!prop->value()->IsValidJSON()) |
| return false; |
| } |
| return true; |
| } |
| |
| |
| bool ArrayLiteral::IsValidJSON() { |
| int length = values()->length(); |
| for (int i = 0; i < length; i++) { |
| if (!values()->at(i)->IsValidJSON()) |
| return false; |
| } |
| return true; |
| } |
| |
| |
| void TargetCollector::AddTarget(BreakTarget* target) { |
| // Add the label to the collector, but discard duplicates. |
| int length = targets_->length(); |
| for (int i = 0; i < length; i++) { |
| if (targets_->at(i) == target) return; |
| } |
| targets_->Add(target); |
| } |
| |
| |
| // ---------------------------------------------------------------------------- |
| // Implementation of AstVisitor |
| |
| |
| void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) { |
| for (int i = 0; i < statements->length(); i++) { |
| Visit(statements->at(i)); |
| } |
| } |
| |
| |
| void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) { |
| for (int i = 0; i < expressions->length(); i++) { |
| // The variable statement visiting code may pass NULL expressions |
| // to this code. Maybe this should be handled by introducing an |
| // undefined expression or literal? Revisit this code if this |
| // changes |
| Expression* expression = expressions->at(i); |
| if (expression != NULL) Visit(expression); |
| } |
| } |
| |
| |
| // ---------------------------------------------------------------------------- |
| // Regular expressions |
| |
| #define MAKE_ACCEPT(Name) \ |
| void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ |
| return visitor->Visit##Name(this, data); \ |
| } |
| FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) |
| #undef MAKE_ACCEPT |
| |
| #define MAKE_TYPE_CASE(Name) \ |
| RegExp##Name* RegExpTree::As##Name() { \ |
| return NULL; \ |
| } \ |
| bool RegExpTree::Is##Name() { return false; } |
| FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) |
| #undef MAKE_TYPE_CASE |
| |
| #define MAKE_TYPE_CASE(Name) \ |
| RegExp##Name* RegExp##Name::As##Name() { \ |
| return this; \ |
| } \ |
| bool RegExp##Name::Is##Name() { return true; } |
| FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) |
| #undef MAKE_TYPE_CASE |
| |
| RegExpEmpty RegExpEmpty::kInstance; |
| |
| |
| static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) { |
| Interval result = Interval::Empty(); |
| for (int i = 0; i < children->length(); i++) |
| result = result.Union(children->at(i)->CaptureRegisters()); |
| return result; |
| } |
| |
| |
| Interval RegExpAlternative::CaptureRegisters() { |
| return ListCaptureRegisters(nodes()); |
| } |
| |
| |
| Interval RegExpDisjunction::CaptureRegisters() { |
| return ListCaptureRegisters(alternatives()); |
| } |
| |
| |
| Interval RegExpLookahead::CaptureRegisters() { |
| return body()->CaptureRegisters(); |
| } |
| |
| |
| Interval RegExpCapture::CaptureRegisters() { |
| Interval self(StartRegister(index()), EndRegister(index())); |
| return self.Union(body()->CaptureRegisters()); |
| } |
| |
| |
| Interval RegExpQuantifier::CaptureRegisters() { |
| return body()->CaptureRegisters(); |
| } |
| |
| |
| bool RegExpAssertion::IsAnchored() { |
| return type() == RegExpAssertion::START_OF_INPUT; |
| } |
| |
| |
| bool RegExpAlternative::IsAnchored() { |
| ZoneList<RegExpTree*>* nodes = this->nodes(); |
| for (int i = 0; i < nodes->length(); i++) { |
| RegExpTree* node = nodes->at(i); |
| if (node->IsAnchored()) { return true; } |
| if (node->max_match() > 0) { return false; } |
| } |
| return false; |
| } |
| |
| |
| bool RegExpDisjunction::IsAnchored() { |
| ZoneList<RegExpTree*>* alternatives = this->alternatives(); |
| for (int i = 0; i < alternatives->length(); i++) { |
| if (!alternatives->at(i)->IsAnchored()) |
| return false; |
| } |
| return true; |
| } |
| |
| |
| bool RegExpLookahead::IsAnchored() { |
| return is_positive() && body()->IsAnchored(); |
| } |
| |
| |
| bool RegExpCapture::IsAnchored() { |
| return body()->IsAnchored(); |
| } |
| |
| |
| // Convert regular expression trees to a simple sexp representation. |
| // This representation should be different from the input grammar |
| // in as many cases as possible, to make it more difficult for incorrect |
| // parses to look as correct ones which is likely if the input and |
| // output formats are alike. |
| class RegExpUnparser: public RegExpVisitor { |
| public: |
| RegExpUnparser(); |
| void VisitCharacterRange(CharacterRange that); |
| SmartPointer<const char> ToString() { return stream_.ToCString(); } |
| #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data); |
| FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) |
| #undef MAKE_CASE |
| private: |
| StringStream* stream() { return &stream_; } |
| HeapStringAllocator alloc_; |
| StringStream stream_; |
| }; |
| |
| |
| RegExpUnparser::RegExpUnparser() : stream_(&alloc_) { |
| } |
| |
| |
| void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { |
| stream()->Add("(|"); |
| for (int i = 0; i < that->alternatives()->length(); i++) { |
| stream()->Add(" "); |
| that->alternatives()->at(i)->Accept(this, data); |
| } |
| stream()->Add(")"); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { |
| stream()->Add("(:"); |
| for (int i = 0; i < that->nodes()->length(); i++) { |
| stream()->Add(" "); |
| that->nodes()->at(i)->Accept(this, data); |
| } |
| stream()->Add(")"); |
| return NULL; |
| } |
| |
| |
| void RegExpUnparser::VisitCharacterRange(CharacterRange that) { |
| stream()->Add("%k", that.from()); |
| if (!that.IsSingleton()) { |
| stream()->Add("-%k", that.to()); |
| } |
| } |
| |
| |
| |
| void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, |
| void* data) { |
| if (that->is_negated()) |
| stream()->Add("^"); |
| stream()->Add("["); |
| for (int i = 0; i < that->ranges()->length(); i++) { |
| if (i > 0) stream()->Add(" "); |
| VisitCharacterRange(that->ranges()->at(i)); |
| } |
| stream()->Add("]"); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { |
| switch (that->type()) { |
| case RegExpAssertion::START_OF_INPUT: |
| stream()->Add("@^i"); |
| break; |
| case RegExpAssertion::END_OF_INPUT: |
| stream()->Add("@$i"); |
| break; |
| case RegExpAssertion::START_OF_LINE: |
| stream()->Add("@^l"); |
| break; |
| case RegExpAssertion::END_OF_LINE: |
| stream()->Add("@$l"); |
| break; |
| case RegExpAssertion::BOUNDARY: |
| stream()->Add("@b"); |
| break; |
| case RegExpAssertion::NON_BOUNDARY: |
| stream()->Add("@B"); |
| break; |
| } |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) { |
| stream()->Add("'"); |
| Vector<const uc16> chardata = that->data(); |
| for (int i = 0; i < chardata.length(); i++) { |
| stream()->Add("%k", chardata[i]); |
| } |
| stream()->Add("'"); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitText(RegExpText* that, void* data) { |
| if (that->elements()->length() == 1) { |
| that->elements()->at(0).data.u_atom->Accept(this, data); |
| } else { |
| stream()->Add("(!"); |
| for (int i = 0; i < that->elements()->length(); i++) { |
| stream()->Add(" "); |
| that->elements()->at(i).data.u_atom->Accept(this, data); |
| } |
| stream()->Add(")"); |
| } |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) { |
| stream()->Add("(# %i ", that->min()); |
| if (that->max() == RegExpTree::kInfinity) { |
| stream()->Add("- "); |
| } else { |
| stream()->Add("%i ", that->max()); |
| } |
| stream()->Add(that->is_greedy() ? "g " : "n "); |
| that->body()->Accept(this, data); |
| stream()->Add(")"); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { |
| stream()->Add("(^ "); |
| that->body()->Accept(this, data); |
| stream()->Add(")"); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { |
| stream()->Add("(-> "); |
| stream()->Add(that->is_positive() ? "+ " : "- "); |
| that->body()->Accept(this, data); |
| stream()->Add(")"); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, |
| void* data) { |
| stream()->Add("(<- %i)", that->index()); |
| return NULL; |
| } |
| |
| |
| void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) { |
| stream()->Put('%'); |
| return NULL; |
| } |
| |
| |
| SmartPointer<const char> RegExpTree::ToString() { |
| RegExpUnparser unparser; |
| Accept(&unparser, NULL); |
| return unparser.ToString(); |
| } |
| |
| |
| RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) |
| : alternatives_(alternatives) { |
| ASSERT(alternatives->length() > 1); |
| RegExpTree* first_alternative = alternatives->at(0); |
| min_match_ = first_alternative->min_match(); |
| max_match_ = first_alternative->max_match(); |
| for (int i = 1; i < alternatives->length(); i++) { |
| RegExpTree* alternative = alternatives->at(i); |
| min_match_ = Min(min_match_, alternative->min_match()); |
| max_match_ = Max(max_match_, alternative->max_match()); |
| } |
| } |
| |
| |
| RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes) |
| : nodes_(nodes) { |
| ASSERT(nodes->length() > 1); |
| min_match_ = 0; |
| max_match_ = 0; |
| for (int i = 0; i < nodes->length(); i++) { |
| RegExpTree* node = nodes->at(i); |
| min_match_ += node->min_match(); |
| int node_max_match = node->max_match(); |
| if (kInfinity - max_match_ < node_max_match) { |
| max_match_ = kInfinity; |
| } else { |
| max_match_ += node->max_match(); |
| } |
| } |
| } |
| |
| |
| } } // namespace v8::internal |