[regexp] step back if starting unicode regexp within surrogate pair.

src/regexp/jsregexp.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/regexp/jsregexp.h"
 
 #include "src/ast/ast.h"
 #include "src/base/platform/platform.h"
 #include "src/compilation-cache.h"
 #include "src/compiler.h"
@@ skipping 5014 matching lines @@
   int stack_register = compiler->UnicodeLookaroundStackRegister();
   int position_register = compiler->UnicodeLookaroundPositionRegister();
   RegExpLookaround::Builder lookaround(false, on_success, stack_register,
                                        position_register);
   RegExpNode* negative_match = TextNode::CreateForCharacterRanges(
       zone, lookahead, read_backward, lookaround.on_match_success());
   return TextNode::CreateForCharacterRanges(
       zone, match, read_backward, lookaround.ForMatch(negative_match));
 }
 
-
 void AddLoneLeadSurrogates(RegExpCompiler* compiler, ChoiceNode* result,
                            RegExpNode* on_success,
                            UnicodeRangeSplitter* splitter) {
   ZoneList<CharacterRange>* lead_surrogates = splitter->lead_surrogates();
   if (lead_surrogates == nullptr) return;
   Zone* zone = compiler->zone();
   // E.g. \ud801 becomes \ud801(?![\udc00-\udfff]).
-  ZoneList<CharacterRange>* trail_surrogates =
-      new (zone) ZoneList<CharacterRange>(1, zone);
-  trail_surrogates->Add(
-      CharacterRange::Range(kTrailSurrogateStart, kTrailSurrogateEnd), zone);
+  ZoneList<CharacterRange>* trail_surrogates = CharacterRange::List(
+      zone, CharacterRange::Range(kTrailSurrogateStart, kTrailSurrogateEnd));
 
   RegExpNode* match =
       compiler->read_backward()
           // Reading backward. Assert that reading forward, there is no trail
           // surrogate, and then backward match the lead surrogate.
           ? NegativeLookaroundAgainstReadDirectionAndMatch(
                 compiler, trail_surrogates, lead_surrogates, on_success, true)
           // Reading forward. Forwrad match the lead surrogate and assert that

[erikcorry, 2016/01/22 10:10:10]

Forwrad -> Forward

Also, this ternary expression is too big, and would be better as an 'if' IMHO

[Yang, 2016/01/25 07:38:41]

Done.

           // no

[erikcorry, 2016/01/22 10:10:10]

Unfortunate line break.  (Autoformatter doesn't really understand block
comments.  If you are using vim then gq is smarter.)

[Yang, 2016/01/25 07:38:41]

Done.

And thanks for the vim tip :)

           // trail surrogate follows.
           : MatchAndNegativeLookaroundInReadDirection(
                 compiler, lead_surrogates, trail_surrogates, on_success, false);
   result->AddAlternative(GuardedAlternative(match));
 }
 
 
 void AddLoneTrailSurrogates(RegExpCompiler* compiler, ChoiceNode* result,
                             RegExpNode* on_success,
                             UnicodeRangeSplitter* splitter) {
   ZoneList<CharacterRange>* trail_surrogates = splitter->trail_surrogates();
   if (trail_surrogates == nullptr) return;
   Zone* zone = compiler->zone();
   // E.g. \udc01 becomes (?<![\ud800-\udbff])\udc01
-  ZoneList<CharacterRange>* lead_surrogates =
-      new (zone) ZoneList<CharacterRange>(1, zone);
-  lead_surrogates->Add(
-      CharacterRange::Range(kLeadSurrogateStart, kLeadSurrogateEnd), zone);
+  ZoneList<CharacterRange>* lead_surrogates = CharacterRange::List(
+      zone, CharacterRange::Range(kLeadSurrogateStart, kLeadSurrogateEnd));
 
   RegExpNode* match =
       compiler->read_backward()
           // Reading backward. Backward match the trail surrogate and assert
           // that no lead surrogate precedes it.
           ? MatchAndNegativeLookaroundInReadDirection(
                 compiler, trail_surrogates, lead_surrogates, on_success, true)
           // Reading forward. Assert that reading backward, there is no lead
           // surrogate, and then forward match the trail surrogate.
           : NegativeLookaroundAgainstReadDirectionAndMatch(
                 compiler, lead_surrogates, trail_surrogates, on_success, false);
   result->AddAlternative(GuardedAlternative(match));
 }
 
 
+void AddUnanchoredAdvance(RegExpCompiler* compiler, ChoiceNode* result,
+                          RegExpNode* on_success) {
+  // This implements ES2015 21.2.5.2.3, AdvanceStringIndex.
+  DCHECK(!compiler->read_backward());
+  Zone* zone = compiler->zone();
+  // Advancing can either consume a BMP character or a trail surrogate.
+  ZoneList<CharacterRange>* bmp_and_trail =
+      new (zone) ZoneList<CharacterRange>(2, zone);
+  bmp_and_trail->Add(CharacterRange::Range(0, kLeadSurrogateStart - 1), zone);
+  bmp_and_trail->Add(
+      CharacterRange::Range(kLeadSurrogateEnd + 1, kNonBmpStart - 1), zone);
+  result->AddAlternative(GuardedAlternative(TextNode::CreateForCharacterRanges(
+      zone, bmp_and_trail, false, on_success)));
+
+  // Or it could consume a lead optionally followed by a trail surrogate.
+  ZoneList<CharacterRange>* lead_surrogates = CharacterRange::List(
+      zone, CharacterRange::Range(kLeadSurrogateStart, kLeadSurrogateEnd));
+  ZoneList<CharacterRange>* trail_surrogates = CharacterRange::List(
+      zone, CharacterRange::Range(kTrailSurrogateStart, kTrailSurrogateEnd));
+  ChoiceNode* optional_trail = new (zone) ChoiceNode(2, zone);
+  optional_trail->AddAlternative(
+      GuardedAlternative(TextNode::CreateForCharacterRanges(
+          zone, trail_surrogates, false, on_success)));
+  optional_trail->AddAlternative(GuardedAlternative(on_success));
+  RegExpNode* optional_pair = TextNode::CreateForCharacterRanges(
+      zone, lead_surrogates, false, optional_trail);
+  result->AddAlternative(GuardedAlternative(optional_pair));
+}
+
+
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success) {
   set_.Canonicalize();
   Zone* zone = compiler->zone();
   ZoneList<CharacterRange>* ranges = this->ranges(zone);
   if (compiler->unicode() && !compiler->one_byte()) {
     if (is_negated()) {
       ZoneList<CharacterRange>* negated =
           new (zone) ZoneList<CharacterRange>(2, zone);
       CharacterRange::Negate(ranges, negated, zone);
       ranges = negated;
     }
     if (ranges->length() == 0) {
       // No matches possible.
       return new (zone) EndNode(EndNode::BACKTRACK, zone);
     }
-    UnicodeRangeSplitter splitter(zone, ranges);
-    ChoiceNode* result = new (compiler->zone()) ChoiceNode(2, compiler->zone());
-    AddBmpCharacters(compiler, result, on_success, &splitter);
-    AddNonBmpSurrogatePairs(compiler, result, on_success, &splitter);
-    AddLoneLeadSurrogates(compiler, result, on_success, &splitter);
-    AddLoneTrailSurrogates(compiler, result, on_success, &splitter);
+    ChoiceNode* result = new (zone) ChoiceNode(2, zone);
+    if (standard_type() == '*') {
+      AddUnanchoredAdvance(compiler, result, on_success);

[erikcorry, 2016/01/22 10:10:10]

Is this better than what the other half of the 'if' would add?

[Yang, 2016/01/25 07:38:41]

This adds
[\0-\ud7ff\uc000\uffff]|[\ud800-\udbff][\udc00-\udfff]?
instead of
[\0-\ud7ff\ue000\uffff]|[\ud800-\udbff][\udc00-\udfff]|(?!<[\ud800-\udbff])[\udc00-\udfff]|[\ud800-\udbff](?![\udc00-\udfff])

Or
[BMP+T]|TL?
instead of
[BMP]|TL|(?!<T)L|T(?!L)

So I think this is a win.

+    } else {
+      UnicodeRangeSplitter splitter(zone, ranges);
+      AddBmpCharacters(compiler, result, on_success, &splitter);
+      AddNonBmpSurrogatePairs(compiler, result, on_success, &splitter);
+      AddLoneLeadSurrogates(compiler, result, on_success, &splitter);
+      AddLoneTrailSurrogates(compiler, result, on_success, &splitter);
+    }
     return result;

[erikcorry, 2016/01/22 10:10:10]

I think it's worth checking if the choice node has only one alternative, and
returning that instead in that case.  Eg. \d or [,.] will only have one
alternative, and we will get better code I think (no flushing).

[Yang, 2016/01/25 07:38:41]

Done in ChoiceNode::Emit.

   } else {
     return new (zone) TextNode(this, compiler->read_backward(), on_success);
   }
 }
 
 
 int CompareFirstChar(RegExpTree* const* a, RegExpTree* const* b) {
   RegExpAtom* atom1 = (*a)->AsAtom();
   RegExpAtom* atom2 = (*b)->AsAtom();
   uc16 character1 = atom1->data().at(0);
@@ skipping 1384 matching lines @@
   }
 }
 
 
 void DispatchTableConstructor::VisitAction(ActionNode* that) {
   RegExpNode* target = that->on_success();
   target->Accept(this);
 }
 
 
+RegExpNode* OptionallyStepBackToLeadSurrogate(RegExpCompiler* compiler,

[erikcorry, 2016/01/22 10:10:10]

Going backwards is some standards-mandated strangeness for sure.  Wil this
always make progress on global matches?  Eg if I search for /()/ with /g and I
start in the middle of a pair?

[Yang, 2016/01/25 07:38:41]

You are right. I have to figure out this one. In case of /()/g we generally have
to step to the next code point, so the current implementation of stepping just a
single character is incorrect to begin with. I'll work on this in a separate CL.

+                                              RegExpNode* on_success) {
+  // If the regexp matching starts within a surrogate pair, step back
+  // to the lead surrogate and start matching from there.
+  DCHECK(!compiler->read_backward());
+  Zone* zone = compiler->zone();
+  ZoneList<CharacterRange>* lead_surrogates = CharacterRange::List(
+      zone, CharacterRange::Range(kLeadSurrogateStart, kLeadSurrogateEnd));
+  ZoneList<CharacterRange>* trail_surrogates = CharacterRange::List(
+      zone, CharacterRange::Range(kTrailSurrogateStart, kTrailSurrogateEnd));
+
+  ChoiceNode* optional_step_back = new (zone) ChoiceNode(2, zone);
+
+  int stack_register = compiler->UnicodeLookaroundStackRegister();
+  int position_register = compiler->UnicodeLookaroundPositionRegister();

[erikcorry, 2016/01/22 10:10:10]

How does this actually do the backwards step?  Some cleverness with the position
register?

[Yang, 2016/01/25 07:38:41]

The TextNode for lead surrogates below consumes one character backward.

+  RegExpNode* step_back = TextNode::CreateForCharacterRanges(
+      zone, lead_surrogates, true, on_success);
+  RegExpLookaround::Builder builder(true, step_back, stack_register,
+                                    position_register);
+  RegExpNode* match_trail = TextNode::CreateForCharacterRanges(
+      zone, trail_surrogates, false, builder.on_match_success());
+
+  optional_step_back->AddAlternative(
+      GuardedAlternative(builder.ForMatch(match_trail)));
+  optional_step_back->AddAlternative(GuardedAlternative(on_success));
+
+  return optional_step_back;
+}
+
+
 RegExpEngine::CompilationResult RegExpEngine::Compile(
     Isolate* isolate, Zone* zone, RegExpCompileData* data,
     JSRegExp::Flags flags, Handle<String> pattern,
     Handle<String> sample_subject, bool is_one_byte) {
   if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) {
     return IrregexpRegExpTooBig(isolate);
   }
   bool ignore_case = flags & JSRegExp::kIgnoreCase;
   bool is_sticky = flags & JSRegExp::kSticky;
   bool is_global = flags & JSRegExp::kGlobal;
@@ skipping 42 matching lines @@
       node = loop_node;
     }
   }
   if (is_one_byte) {
     node = node->FilterOneByte(RegExpCompiler::kMaxRecursion, ignore_case);
     // Do it again to propagate the new nodes to places where they were not
     // put because they had not been calculated yet.
     if (node != NULL) {
       node = node->FilterOneByte(RegExpCompiler::kMaxRecursion, ignore_case);
     }
+  } else if (compiler.unicode()) {
+    node = OptionallyStepBackToLeadSurrogate(&compiler, node);

[erikcorry, 2016/01/22 10:10:10]

Do we need this for non-sticky non-global regexps?  Don't they always start at
the beginning?

[Yang, 2016/01/25 07:38:41]

Done.

   }
 
   if (node == NULL) node = new(zone) EndNode(EndNode::BACKTRACK, zone);
   data->node = node;
   Analysis analysis(isolate, ignore_case, is_one_byte);
   analysis.EnsureAnalyzed(node);
   if (analysis.has_failed()) {
     const char* error_message = analysis.error_message();
     return CompilationResult(isolate, error_message);
   }
@@ skipping 171 matching lines @@
 
 
 void RegExpResultsCache::Clear(FixedArray* cache) {
   for (int i = 0; i < kRegExpResultsCacheSize; i++) {
     cache->set(i, Smi::FromInt(0));
   }
 }
 
 }  // namespace internal
 }  // namespace v8