Regexp: Remove nodes from the regexp that cannot match because

src/jsregexp.cc

 // Copyright 2011 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
@@ skipping 362 matching lines @@
   elements->set(0, re->Pattern());
   elements->set(1, *error_message);
   Handle<JSArray> array = factory->NewJSArrayWithElements(elements);
   Handle<Object> regexp_err =
       factory->NewSyntaxError("malformed_regexp", array);
   isolate->Throw(*regexp_err);
   return false;
 }
 
 
+int kUninitializedRegExpNodePlaceHolder;
+
+
 bool RegExpImpl::CompileIrregexp(Handle<JSRegExp> re,
                                  Handle<String> sample_subject,
                                  bool is_ascii) {
   // Compile the RegExp.
   Isolate* isolate = re->GetIsolate();
   ZoneScope zone_scope(isolate, DELETE_ON_EXIT);
   PostponeInterruptsScope postpone(isolate);
   // If we had a compilation error the last time this is saved at the
   // saved code index.
   Object* entry = re->DataAt(JSRegExp::code_index(is_ascii));
@@ skipping 2026 matching lines @@
     char_mask = String::kMaxUtf16CodeUnit;
   }
   for (int k = 0; k < elms_->length(); k++) {
     TextElement elm = elms_->at(k);
     if (elm.type == TextElement::ATOM) {
       Vector<const uc16> quarks = elm.data.u_atom->data();
       for (int i = 0; i < characters && i < quarks.length(); i++) {
         QuickCheckDetails::Position* pos =
             details->positions(characters_filled_in);
         uc16 c = quarks[i];
-        if (c > char_mask) {
-          // If we expect a non-ASCII character from an ASCII string,
-          // there is no way we can match. Not even case independent
-          // matching can turn an ASCII character into non-ASCII or
-          // vice versa.
-          details->set_cannot_match();
-          pos->determines_perfectly = false;
-          return;
-        }
+        // We should already have filtered out nodes that have non-ASCII
+        // characters if we are matching against an ASCII string.
+        ASSERT(c <= char_mask);
         if (compiler->ignore_case()) {
           unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
           int length = GetCaseIndependentLetters(isolate, c, compiler->ascii(),
                                                  chars);
           ASSERT(length != 0);  // Can only happen if c > char_mask (see above).
           if (length == 1) {
             // This letter has no case equivalents, so it's nice and simple
             // and the mask-compare will determine definitely whether we have
             // a match at this character position.
             pos->mask = char_mask;
@@ skipping 41 matching lines @@
         // A quick check uses multi-character mask and compare.  There is no
         // useful way to incorporate a negative char class into this scheme
         // so we just conservatively create a mask and value that will always
         // succeed.
         pos->mask = 0;
         pos->value = 0;
       } else {
         int first_range = 0;
         while (ranges->at(first_range).from() > char_mask) {
           first_range++;
-          if (first_range == ranges->length()) {
-            details->set_cannot_match();
-            pos->determines_perfectly = false;
-            return;
-          }
+          // We should already have filtered out nodes that cannot match
+          // so the first range should be a valid range.
+          ASSERT(first_range != ranges->length());
         }
         CharacterRange range = ranges->at(first_range);
         uc16 from = range.from();
         uc16 to = range.to();
         if (to > char_mask) {
           to = char_mask;
         }
         uint32_t differing_bits = (from ^ to);
         // A mask and compare is only perfect if the differing bits form a
         // number like 00011111 with one single block of trailing 1s.
@@ skipping 108 matching lines @@
     info->visited = true;
   }
   ~VisitMarker() {
     info_->visited = false;
   }
  private:
   NodeInfo* info_;
 };
 
 
+RegExpNode* SeqRegExpNode::FilterASCII(int depth) {
+  if (replacement_ != Uninitialized()) return replacement_;
+  if (depth < 0) return this;
+  ASSERT(!info()->visited);
+  VisitMarker marker(info());
+  return FilterSuccessor(depth - 1);
+}
+
+
+RegExpNode* SeqRegExpNode::FilterSuccessor(int depth) {
+  RegExpNode* next = on_success_->FilterASCII(depth - 1);
+  if (next == NULL) {
+    replacement_ = NULL;
+    return NULL;
+  }
+  on_success_ = next;
+  replacement_ = this;
+  return this;
+}
+
+
+RegExpNode* TextNode::FilterASCII(int depth) {
+  if (replacement_ != Uninitialized()) return replacement_;
+  if (depth < 0) return this;
+  ASSERT(!info()->visited);
+  VisitMarker marker(info());
+  int element_count = elms_->length();
+  for (int i = 0; i < element_count; i++) {
+    TextElement elm = elms_->at(i);
+    if (elm.type == TextElement::ATOM) {
+      Vector<const uc16> quarks = elm.data.u_atom->data();
+      for (int j = 0; j < quarks.length(); j++) {
+        // We don't need special handling for case independence
+        // because of the rule that case independence cannot make
+        // a non-ASCII character match an ASCII character.
+        if (quarks[j] > String::kMaxAsciiCharCode) {
+          replacement_ = NULL;
+          return NULL;
+        }
+      }
+    } else {
+      ASSERT(elm.type == TextElement::CHAR_CLASS);
+      RegExpCharacterClass* cc = elm.data.u_char_class;
+      ZoneList<CharacterRange>* ranges = cc->ranges();
+      if (!CharacterRange::IsCanonical(ranges)) {
+        CharacterRange::Canonicalize(ranges);
+      }
+      // Now they are in order so we only need to look at the first.
+      int range_count = ranges->length();
+      if (cc->is_negated()) {
+        if (range_count != 0 &&
+            ranges->at(0).from() == 0 &&
+            ranges->at(0).to() >= String::kMaxAsciiCharCode) {
+          replacement_ = NULL;
+          return NULL;
+        }
+      } else {
+        if (range_count == 0 ||
+            ranges->at(0).from() > String::kMaxAsciiCharCode) {
+          replacement_ = NULL;
+          return NULL;
+        }
+      }
+    }
+  }
+  return FilterSuccessor(depth - 1);
+}
+
+
+RegExpNode* LoopChoiceNode::FilterASCII(int depth) {
+  if (replacement_ != Uninitialized()) return replacement_;
+  if (depth < 0) return this;
+  if (info()->visited) return this;
+  VisitMarker marker(info());
+
+  RegExpNode* continue_replacement = continue_node_->FilterASCII(depth - 1);
+  if (continue_replacement == NULL) {
+    // If we can't continue after the loop then there is no sense in doing the
+    // loop.
+    replacement_ = NULL;
+    return NULL;
+  }
+
+  return ChoiceNode::FilterASCII(depth - 1);
+}
+
+
+RegExpNode* ChoiceNode::FilterASCII(int depth) {
+  if (replacement_ != Uninitialized()) return replacement_;
+  if (depth < 0) return this;
+  if (info()->visited) return this;
+  VisitMarker marker(info());
+  int choice_count = alternatives_->length();
+  int surviving = 0;
+  RegExpNode* survivor = NULL;
+  for (int i = 0; i < choice_count; i++) {

[ulan, 2012/04/25 12:55:28]

Instead of duplicating the same loop twice, can we do in-place filtering here? 

[Erik Corry, 2012/04/26 08:23:11]

I can't see a way to do in-place filtering, since the zonelist does not have a
delete operation.  I'd rather not build a new list unless we have to since it
will cause extra allocation, and I think the typical case will be that we don't
need a new list.  I have simplified the loops instead.

+    GuardedAlternative alternative = alternatives_->at(i);
+    ZoneList<Guard*>* guards = alternative.guards();
+    int guard_count = (guards == NULL) ? 0 : guards->length();
+    if (guard_count == 0) {
+      RegExpNode* replacement = alternative.node()->FilterASCII(depth - 1);
+      if (replacement != NULL && replacement != this) {
+        surviving++;
+        alternatives_->at(i).set_node(replacement);
+        survivor = replacement;
+      }
+    } else {
+      surviving++;
+    }
+  }
+  if (surviving == 0) {
+    replacement_ = NULL;
+    return NULL;
+  }
+  if (surviving == 1 && survivor != NULL) {
+    replacement_ = survivor;
+    return survivor;
+  }
+  replacement_ = this;
+  if (surviving == choice_count) {
+    return this;
+  }
+  // Only some of the nodes survived the filtering.  We need to rebuild the
+  // alternatives list.
+  ZoneList<GuardedAlternative>* new_alternatives =
+      new ZoneList<GuardedAlternative>(surviving);
+  for (int i = 0; i < choice_count; i++) {
+    GuardedAlternative alternative = alternatives_->at(i);
+    ZoneList<Guard*>* guards = alternative.guards();
+    int guard_count = (guards == NULL) ? 0 : guards->length();
+    if (guard_count == 0) {
+      RegExpNode* replacement = alternative.node()->FilterASCII(depth - 1);
+      if (replacement != NULL && replacement != this) {
+        GuardedAlternative new_alternative(replacement);
+        new_alternatives->Add(new_alternative);
+      }
+    } else {
+      new_alternatives->Add(alternative);
+    }
+  }
+  alternatives_ = new_alternatives;
+  return this;
+}
+
+
+RegExpNode* NegativeLookaheadChoiceNode::FilterASCII(int depth) {
+  if (replacement_ != Uninitialized()) return replacement_;
+  if (depth < 0) return this;
+  if (info()->visited) return this;
+  VisitMarker marker(info());
+  // Alternative 0 is the negative lookahead, alternative 1 is what comes
+  // afterwards.
+  RegExpNode* node = alternatives_->at(1).node();
+  RegExpNode* replacement = node->FilterASCII(depth - 1);
+  if (node == NULL) {

[ulan, 2012/04/25 12:55:28]

Did you mean replacement == NULL?

[Erik Corry, 2012/04/26 08:23:11]

Oops, yes.

+    replacement_ = NULL;
+    return NULL;
+  }
+  alternatives_->at(1).set_node(replacement);
+
+  RegExpNode* neg_node = alternatives_->at(0).node();
+  RegExpNode* neg_replacement = neg_node->FilterASCII(depth - 1);
+  // If the negative lookahead is always going to fail then
+  // we don't need to check it.
+  if (neg_replacement == NULL) {
+    replacement_ = replacement;
+    return replacement;
+  }
+  alternatives_->at(0).set_node(neg_replacement);
+  replacement_ = this;
+  return this;
+}
+
+
 void LoopChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                           RegExpCompiler* compiler,
                                           int characters_filled_in,
                                           bool not_at_start) {
   if (body_can_be_zero_length_ || info()->visited) return;
   VisitMarker marker(info());
   return ChoiceNode::GetQuickCheckDetails(details,
                                           compiler,
                                           characters_filled_in,
                                           not_at_start);
@@ skipping 3041 matching lines @@
       // at the start of input.
       ChoiceNode* first_step_node = new ChoiceNode(2);
       first_step_node->AddAlternative(GuardedAlternative(captured_body));
       first_step_node->AddAlternative(GuardedAlternative(
           new TextNode(new RegExpCharacterClass('*'), loop_node)));
       node = first_step_node;
     } else {
       node = loop_node;
     }
   }
+  if (is_ascii) node = node->FilterASCII(RegExpCompiler::kMaxRecursion);
+
+  if (node == NULL) node = new EndNode(EndNode::BACKTRACK);
   data->node = node;
   Analysis analysis(ignore_case, is_ascii);
   analysis.EnsureAnalyzed(node);
   if (analysis.has_failed()) {
     const char* error_message = analysis.error_message();
     return CompilationResult(error_message);
   }
 
   // Create the correct assembler for the architecture.
 #ifndef V8_INTERPRETED_REGEXP
@@ skipping 29 matching lines @@
   }
 
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal