| // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| #include "vm/regexp_ast.h" |
| |
| #include "platform/utils.h" |
| #include "vm/os.h" |
| |
| namespace dart { |
| |
| #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() const { 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() const { return true; } |
| FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) |
| #undef MAKE_TYPE_CASE |
| |
| static Interval ListCaptureRegisters(ZoneGrowableArray<RegExpTree*>* children) { |
| Interval result = Interval::Empty(); |
| for (intptr_t i = 0; i < children->length(); i++) |
| result = result.Union(children->At(i)->CaptureRegisters()); |
| return result; |
| } |
| |
| Interval RegExpAlternative::CaptureRegisters() const { |
| return ListCaptureRegisters(nodes()); |
| } |
| |
| Interval RegExpDisjunction::CaptureRegisters() const { |
| return ListCaptureRegisters(alternatives()); |
| } |
| |
| Interval RegExpLookahead::CaptureRegisters() const { |
| return body()->CaptureRegisters(); |
| } |
| |
| Interval RegExpCapture::CaptureRegisters() const { |
| Interval self(StartRegister(index()), EndRegister(index())); |
| return self.Union(body()->CaptureRegisters()); |
| } |
| |
| Interval RegExpQuantifier::CaptureRegisters() const { |
| return body()->CaptureRegisters(); |
| } |
| |
| bool RegExpAssertion::IsAnchoredAtStart() const { |
| return assertion_type() == RegExpAssertion::START_OF_INPUT; |
| } |
| |
| bool RegExpAssertion::IsAnchoredAtEnd() const { |
| return assertion_type() == RegExpAssertion::END_OF_INPUT; |
| } |
| |
| bool RegExpAlternative::IsAnchoredAtStart() const { |
| ZoneGrowableArray<RegExpTree*>* nodes = this->nodes(); |
| for (intptr_t i = 0; i < nodes->length(); i++) { |
| RegExpTree* node = nodes->At(i); |
| if (node->IsAnchoredAtStart()) { |
| return true; |
| } |
| if (node->max_match() > 0) { |
| return false; |
| } |
| } |
| return false; |
| } |
| |
| bool RegExpAlternative::IsAnchoredAtEnd() const { |
| ZoneGrowableArray<RegExpTree*>* nodes = this->nodes(); |
| for (intptr_t i = nodes->length() - 1; i >= 0; i--) { |
| RegExpTree* node = nodes->At(i); |
| if (node->IsAnchoredAtEnd()) { |
| return true; |
| } |
| if (node->max_match() > 0) { |
| return false; |
| } |
| } |
| return false; |
| } |
| |
| bool RegExpDisjunction::IsAnchoredAtStart() const { |
| ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives(); |
| for (intptr_t i = 0; i < alternatives->length(); i++) { |
| if (!alternatives->At(i)->IsAnchoredAtStart()) return false; |
| } |
| return true; |
| } |
| |
| bool RegExpDisjunction::IsAnchoredAtEnd() const { |
| ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives(); |
| for (intptr_t i = 0; i < alternatives->length(); i++) { |
| if (!alternatives->At(i)->IsAnchoredAtEnd()) return false; |
| } |
| return true; |
| } |
| |
| bool RegExpLookahead::IsAnchoredAtStart() const { |
| return is_positive() && body()->IsAnchoredAtStart(); |
| } |
| |
| bool RegExpCapture::IsAnchoredAtStart() const { |
| return body()->IsAnchoredAtStart(); |
| } |
| |
| bool RegExpCapture::IsAnchoredAtEnd() const { |
| return body()->IsAnchoredAtEnd(); |
| } |
| |
| // 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: |
| void VisitCharacterRange(CharacterRange that); |
| #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data); |
| FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) |
| #undef MAKE_CASE |
| }; |
| |
| void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { |
| OS::PrintErr("(|"); |
| for (intptr_t i = 0; i < that->alternatives()->length(); i++) { |
| OS::PrintErr(" "); |
| (*that->alternatives())[i]->Accept(this, data); |
| } |
| OS::PrintErr(")"); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { |
| OS::PrintErr("(:"); |
| for (intptr_t i = 0; i < that->nodes()->length(); i++) { |
| OS::PrintErr(" "); |
| (*that->nodes())[i]->Accept(this, data); |
| } |
| OS::PrintErr(")"); |
| return NULL; |
| } |
| |
| void RegExpUnparser::VisitCharacterRange(CharacterRange that) { |
| PrintUtf16(that.from()); |
| if (!that.IsSingleton()) { |
| OS::PrintErr("-"); |
| PrintUtf16(that.to()); |
| } |
| } |
| |
| void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, |
| void* data) { |
| if (that->is_negated()) OS::PrintErr("^"); |
| OS::PrintErr("["); |
| for (intptr_t i = 0; i < that->ranges()->length(); i++) { |
| if (i > 0) OS::PrintErr(" "); |
| VisitCharacterRange((*that->ranges())[i]); |
| } |
| OS::PrintErr("]"); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { |
| switch (that->assertion_type()) { |
| case RegExpAssertion::START_OF_INPUT: |
| OS::PrintErr("@^i"); |
| break; |
| case RegExpAssertion::END_OF_INPUT: |
| OS::PrintErr("@$i"); |
| break; |
| case RegExpAssertion::START_OF_LINE: |
| OS::PrintErr("@^l"); |
| break; |
| case RegExpAssertion::END_OF_LINE: |
| OS::PrintErr("@$l"); |
| break; |
| case RegExpAssertion::BOUNDARY: |
| OS::PrintErr("@b"); |
| break; |
| case RegExpAssertion::NON_BOUNDARY: |
| OS::PrintErr("@B"); |
| break; |
| } |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) { |
| OS::PrintErr("'"); |
| ZoneGrowableArray<uint16_t>* chardata = that->data(); |
| for (intptr_t i = 0; i < chardata->length(); i++) { |
| PrintUtf16(chardata->At(i)); |
| } |
| OS::PrintErr("'"); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitText(RegExpText* that, void* data) { |
| if (that->elements()->length() == 1) { |
| (*that->elements())[0].tree()->Accept(this, data); |
| } else { |
| OS::PrintErr("(!"); |
| for (intptr_t i = 0; i < that->elements()->length(); i++) { |
| OS::PrintErr(" "); |
| (*that->elements())[i].tree()->Accept(this, data); |
| } |
| OS::PrintErr(")"); |
| } |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) { |
| OS::PrintErr("(# %" Pd " ", that->min()); |
| if (that->max() == RegExpTree::kInfinity) { |
| OS::PrintErr("- "); |
| } else { |
| OS::PrintErr("%" Pd " ", that->max()); |
| } |
| OS::PrintErr(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n "); |
| that->body()->Accept(this, data); |
| OS::PrintErr(")"); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { |
| OS::PrintErr("(^ "); |
| that->body()->Accept(this, data); |
| OS::PrintErr(")"); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { |
| OS::PrintErr("(-> %s", (that->is_positive() ? "+ " : "- ")); |
| that->body()->Accept(this, data); |
| OS::PrintErr(")"); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, void*) { |
| OS::PrintErr("(<- %" Pd ")", that->index()); |
| return NULL; |
| } |
| |
| void* RegExpUnparser::VisitEmpty(RegExpEmpty*, void*) { |
| OS::PrintErr("%%"); |
| return NULL; |
| } |
| |
| void RegExpTree::Print() { |
| RegExpUnparser unparser; |
| Accept(&unparser, NULL); |
| } |
| |
| RegExpDisjunction::RegExpDisjunction( |
| ZoneGrowableArray<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 (intptr_t i = 1; i < alternatives->length(); i++) { |
| RegExpTree* alternative = alternatives->At(i); |
| min_match_ = Utils::Minimum(min_match_, alternative->min_match()); |
| max_match_ = Utils::Maximum(max_match_, alternative->max_match()); |
| } |
| } |
| |
| static intptr_t IncreaseBy(intptr_t previous, intptr_t increase) { |
| if (RegExpTree::kInfinity - previous < increase) { |
| return RegExpTree::kInfinity; |
| } else { |
| return previous + increase; |
| } |
| } |
| |
| RegExpAlternative::RegExpAlternative(ZoneGrowableArray<RegExpTree*>* nodes) |
| : nodes_(nodes) { |
| ASSERT(nodes->length() > 1); |
| min_match_ = 0; |
| max_match_ = 0; |
| for (intptr_t i = 0; i < nodes->length(); i++) { |
| RegExpTree* node = nodes->At(i); |
| intptr_t node_min_match = node->min_match(); |
| min_match_ = IncreaseBy(min_match_, node_min_match); |
| intptr_t node_max_match = node->max_match(); |
| max_match_ = IncreaseBy(max_match_, node_max_match); |
| } |
| } |
| |
| } // namespace dart |