5 #include "src/ostreams.h" 6 #include "src/regexp/regexp-ast.h" 11 #define MAKE_ACCEPT(Name) \ 12 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ 13 return visitor->Visit##Name(this, data); \ 15 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
18 #define MAKE_TYPE_CASE(Name) \ 19 RegExp##Name* RegExpTree::As##Name() { return nullptr; } \ 20 bool RegExpTree::Is##Name() { return false; } 21 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
24 #define MAKE_TYPE_CASE(Name) \ 25 RegExp##Name* RegExp##Name::As##Name() { return this; } \ 26 bool RegExp##Name::Is##Name() { return true; } 27 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
31 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
32 Interval result = Interval::Empty();
33 for (
int i = 0;
i < children->length();
i++)
34 result = result.Union(children->at(
i)->CaptureRegisters());
39 Interval RegExpAlternative::CaptureRegisters() {
40 return ListCaptureRegisters(nodes());
44 Interval RegExpDisjunction::CaptureRegisters() {
45 return ListCaptureRegisters(alternatives());
49 Interval RegExpLookaround::CaptureRegisters() {
50 return body()->CaptureRegisters();
54 Interval RegExpCapture::CaptureRegisters() {
55 Interval
self(StartRegister(index()), EndRegister(index()));
56 return self.Union(body()->CaptureRegisters());
60 Interval RegExpQuantifier::CaptureRegisters() {
61 return body()->CaptureRegisters();
65 bool RegExpAssertion::IsAnchoredAtStart() {
66 return assertion_type() == RegExpAssertion::START_OF_INPUT;
70 bool RegExpAssertion::IsAnchoredAtEnd() {
71 return assertion_type() == RegExpAssertion::END_OF_INPUT;
75 bool RegExpAlternative::IsAnchoredAtStart() {
76 ZoneList<RegExpTree*>* nodes = this->nodes();
77 for (
int i = 0;
i < nodes->length();
i++) {
78 RegExpTree* node = nodes->at(
i);
79 if (node->IsAnchoredAtStart()) {
82 if (node->max_match() > 0) {
90 bool RegExpAlternative::IsAnchoredAtEnd() {
91 ZoneList<RegExpTree*>* nodes = this->nodes();
92 for (
int i = nodes->length() - 1;
i >= 0;
i--) {
93 RegExpTree* node = nodes->at(
i);
94 if (node->IsAnchoredAtEnd()) {
97 if (node->max_match() > 0) {
105 bool RegExpDisjunction::IsAnchoredAtStart() {
106 ZoneList<RegExpTree*>* alternatives = this->alternatives();
107 for (
int i = 0;
i < alternatives->length();
i++) {
108 if (!alternatives->at(
i)->IsAnchoredAtStart())
return false;
114 bool RegExpDisjunction::IsAnchoredAtEnd() {
115 ZoneList<RegExpTree*>* alternatives = this->alternatives();
116 for (
int i = 0;
i < alternatives->length();
i++) {
117 if (!alternatives->at(
i)->IsAnchoredAtEnd())
return false;
123 bool RegExpLookaround::IsAnchoredAtStart() {
124 return is_positive() && type() == LOOKAHEAD && body()->IsAnchoredAtStart();
128 bool RegExpCapture::IsAnchoredAtStart() {
return body()->IsAnchoredAtStart(); }
131 bool RegExpCapture::IsAnchoredAtEnd() {
return body()->IsAnchoredAtEnd(); }
143 #define MAKE_CASE(Name) void* Visit##Name(RegExp##Name*, void* data) override; 144 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
154 for (
int i = 0;
i < that->alternatives()->length();
i++) {
156 that->alternatives()->at(
i)->Accept(
this, data);
163 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that,
void* data) {
165 for (
int i = 0;
i < that->nodes()->length();
i++) {
167 that->nodes()->at(
i)->Accept(
this, data);
174 void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
175 os_ << AsUC32(that.from());
176 if (!that.IsSingleton()) {
177 os_ <<
"-" << AsUC32(that.to());
182 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
184 if (that->is_negated()) os_ <<
"^";
186 for (
int i = 0;
i < that->ranges(zone_)->length();
i++) {
187 if (
i > 0) os_ <<
" ";
188 VisitCharacterRange(that->ranges(zone_)->at(
i));
195 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that,
void* data) {
196 switch (that->assertion_type()) {
197 case RegExpAssertion::START_OF_INPUT:
200 case RegExpAssertion::END_OF_INPUT:
203 case RegExpAssertion::START_OF_LINE:
206 case RegExpAssertion::END_OF_LINE:
209 case RegExpAssertion::BOUNDARY:
212 case RegExpAssertion::NON_BOUNDARY:
220 void* RegExpUnparser::VisitAtom(RegExpAtom* that,
void* data) {
222 Vector<const uc16> chardata = that->data();
223 for (
int i = 0;
i < chardata.length();
i++) {
224 os_ << AsUC16(chardata[
i]);
231 void* RegExpUnparser::VisitText(RegExpText* that,
void* data) {
232 if (that->elements()->length() == 1) {
233 that->elements()->at(0).tree()->Accept(
this, data);
236 for (
int i = 0;
i < that->elements()->length();
i++) {
238 that->elements()->at(
i).tree()->Accept(
this, data);
246 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that,
void* data) {
247 os_ <<
"(# " << that->min() <<
" ";
248 if (that->max() == RegExpTree::kInfinity) {
251 os_ << that->max() <<
" ";
253 os_ << (that->is_greedy() ?
"g " : that->is_possessive() ?
"p " :
"n ");
254 that->body()->Accept(
this, data);
260 void* RegExpUnparser::VisitCapture(RegExpCapture* that,
void* data) {
262 that->body()->Accept(
this, data);
267 void* RegExpUnparser::VisitGroup(RegExpGroup* that,
void* data) {
269 that->body()->Accept(
this, data);
274 void* RegExpUnparser::VisitLookaround(RegExpLookaround* that,
void* data) {
276 os_ << (that->type() == RegExpLookaround::LOOKAHEAD ?
"->" :
"<-");
277 os_ << (that->is_positive() ?
" + " :
" - ");
278 that->body()->Accept(
this, data);
284 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
286 os_ <<
"(<- " << that->index() <<
")";
291 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that,
void* data) {
297 std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) {
298 RegExpUnparser unparser(os, zone);
299 Accept(&unparser,
nullptr);
304 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
305 : alternatives_(alternatives) {
306 DCHECK_LT(1, alternatives->length());
307 RegExpTree* first_alternative = alternatives->at(0);
308 min_match_ = first_alternative->min_match();
309 max_match_ = first_alternative->max_match();
310 for (
int i = 1;
i < alternatives->length();
i++) {
311 RegExpTree* alternative = alternatives->at(
i);
312 min_match_ = Min(min_match_, alternative->min_match());
313 max_match_ = Max(max_match_, alternative->max_match());
318 static int IncreaseBy(
int previous,
int increase) {
319 if (RegExpTree::kInfinity - previous < increase) {
320 return RegExpTree::kInfinity;
322 return previous + increase;
327 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
329 DCHECK_LT(1, nodes->length());
332 for (
int i = 0;
i < nodes->length();
i++) {
333 RegExpTree* node = nodes->at(
i);
334 int node_min_match = node->min_match();
335 min_match_ = IncreaseBy(min_match_, node_min_match);
336 int node_max_match = node->max_match();
337 max_match_ = IncreaseBy(max_match_, node_max_match);