VM: Optimize RegExp.matchAsPrefix(...) by generating a sticky RegExp specialization.

runtime/vm/regexp.cc

 // 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.h"
 
 #include "vm/dart_entry.h"
 #include "vm/regexp_assembler.h"
 #include "vm/regexp_assembler_bytecode.h"
 #include "vm/regexp_assembler_ir.h"
@@ skipping 4806 matching lines @@
 
 RegExpEngine::CompilationResult RegExpEngine::CompileIR(
     RegExpCompileData* data,
     const ParsedFunction* parsed_function,
     const ZoneGrowableArray<const ICData*>& ic_data_array) {
   ASSERT(!FLAG_interpret_irregexp);
   Zone* zone = Thread::Current()->zone();
 
   const Function& function = parsed_function->function();
   const intptr_t specialization_cid = function.string_specialization_cid();
+  const intptr_t is_sticky = function.is_sticky_specialization();
   const bool is_one_byte = (specialization_cid == kOneByteStringCid ||
                             specialization_cid == kExternalOneByteStringCid);
   RegExp& regexp = RegExp::Handle(zone, function.regexp());
   const String& pattern = String::Handle(zone, regexp.pattern());
 
   ASSERT(!regexp.IsNull());
   ASSERT(!pattern.IsNull());
 
   const bool ignore_case = regexp.is_ignore_case();
   const bool is_global = regexp.is_global();
 
   RegExpCompiler compiler(data->capture_count, ignore_case, is_one_byte);
 
   // TODO(zerny): Frequency sampling is currently disabled because of several
   // issues. We do not want to store subject strings in the regexp object since
   // they might be long and we should not prevent their garbage collection.
   // Passing them to this function explicitly does not help, since we must
   // generate exactly the same IR for both the unoptimizing and optimizing
   // pipelines (otherwise it gets confused when i.e. deopt id's differ).
   // An option would be to store sampling results in the regexp object, but
   // I'm not sure the performance gains are relevant enough.
 
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body =
       RegExpCapture::ToNode(data->tree, 0, &compiler, compiler.accept());
 
   RegExpNode* node = captured_body;
-  bool is_end_anchored = data->tree->IsAnchoredAtEnd();
-  bool is_start_anchored = data->tree->IsAnchoredAtStart();
+  const bool is_end_anchored = data->tree->IsAnchoredAtEnd();
+  const bool is_start_anchored = data->tree->IsAnchoredAtStart();
   intptr_t max_length = data->tree->max_match();
-  if (!is_start_anchored) {
+  if (!is_start_anchored && !is_sticky) {
     // Add a .*? at the beginning, outside the body capture, unless

[rmacnak, 2016/11/17 00:49:52]

Not sure I see why this property is called sticky, but I do see this would
improve prefix matching speed.

[erikcorry, 2016/11/17 13:56:17]

From es-discuss (!):

I believe the y actually comes from "yylex". ES4 proposals had originally called
for the corresponding property to be named anchored or nosearch before changing
it to sticky to avoid overloading the term anchored (which is commonly used to
describe regexes starting with ^ or ending with $) and to better fit with the
letter y. If the name changed to anchored, I'd prefer /a over /n. Flag n (as in
"(?n)") is already used by .NET for the ExplicitCapture option, which is a
feature that might be worth considering for ES6+. I don't mind "sticky",
personally.

-    // this expression is anchored at the beginning.
+    // this expression is anchored at the beginning or is sticky.
     RegExpNode* loop_node = RegExpQuantifier::ToNode(
         0, RegExpTree::kInfinity, false, new (zone) RegExpCharacterClass('*'),
         &compiler, captured_body, data->contains_anchor);
 
     if (data->contains_anchor) {
       // Unroll loop once, to take care of the case that might start
       // at the start of input.
       ChoiceNode* first_step_node = new (zone) ChoiceNode(2, zone);
       first_step_node->AddAlternative(GuardedAlternative(captured_body));
       first_step_node->AddAlternative(GuardedAlternative(new (zone) TextNode(
@@ skipping 25 matching lines @@
 
   IRRegExpMacroAssembler* macro_assembler =
       new (zone) IRRegExpMacroAssembler(specialization_cid, data->capture_count,
                                         parsed_function, ic_data_array, zone);
 
   // Inserted here, instead of in Assembler, because it depends on information
   // in the AST that isn't replicated in the Node structure.
   static const intptr_t kMaxBacksearchLimit = 1024;
   if (is_end_anchored && !is_start_anchored &&
       max_length < kMaxBacksearchLimit) {
     macro_assembler->SetCurrentPositionFromEnd(max_length);

[erikcorry, 2016/11/17 13:56:17]

This needs fixing here too and we need a test for it.

[Vyacheslav Egorov (Google), 2016/11/17 16:51:33]

As we discussed I have fixed it here and I will port a sticky test from V8.

   }
 
   if (is_global) {
     macro_assembler->set_global_mode(
         (data->tree->min_match() > 0)
             ? RegExpMacroAssembler::GLOBAL_NO_ZERO_LENGTH_CHECK
             : RegExpMacroAssembler::GLOBAL);
   }
 
   RegExpEngine::CompilationResult result =
       compiler.Assemble(macro_assembler, node, data->capture_count, pattern);
 
   if (FLAG_trace_irregexp) {
     macro_assembler->PrintBlocks();
   }
 
   return result;
 }
 
 
 RegExpEngine::CompilationResult RegExpEngine::CompileBytecode(
     RegExpCompileData* data,
     const RegExp& regexp,
     bool is_one_byte,
+    bool is_sticky,
     Zone* zone) {
   ASSERT(FLAG_interpret_irregexp);
   const String& pattern = String::Handle(zone, regexp.pattern());
 
   ASSERT(!regexp.IsNull());
   ASSERT(!pattern.IsNull());
 
   const bool ignore_case = regexp.is_ignore_case();
   const bool is_global = regexp.is_global();
 
   RegExpCompiler compiler(data->capture_count, ignore_case, is_one_byte);
 
   // TODO(zerny): Frequency sampling is currently disabled because of several
   // issues. We do not want to store subject strings in the regexp object since
   // they might be long and we should not prevent their garbage collection.
   // Passing them to this function explicitly does not help, since we must
   // generate exactly the same IR for both the unoptimizing and optimizing
   // pipelines (otherwise it gets confused when i.e. deopt id's differ).
   // An option would be to store sampling results in the regexp object, but
   // I'm not sure the performance gains are relevant enough.
 
   // Wrap the body of the regexp in capture #0.
   RegExpNode* captured_body =
       RegExpCapture::ToNode(data->tree, 0, &compiler, compiler.accept());
 
   RegExpNode* node = captured_body;
   bool is_end_anchored = data->tree->IsAnchoredAtEnd();
   bool is_start_anchored = data->tree->IsAnchoredAtStart();
   intptr_t max_length = data->tree->max_match();
-  if (!is_start_anchored) {
+  if (!is_start_anchored && !is_sticky) {
     // Add a .*? at the beginning, outside the body capture, unless
     // this expression is anchored at the beginning.
     RegExpNode* loop_node = RegExpQuantifier::ToNode(
         0, RegExpTree::kInfinity, false, new (zone) RegExpCharacterClass('*'),
         &compiler, captured_body, data->contains_anchor);
 
     if (data->contains_anchor) {
       // Unroll loop once, to take care of the case that might start
       // at the start of input.
       ChoiceNode* first_step_node = new (zone) ChoiceNode(2, zone);
@@ skipping 52 matching lines @@
   }
 
   return result;
 }
 
 
 static void CreateSpecializedFunction(Thread* thread,
                                       Zone* zone,
                                       const RegExp& regexp,
                                       intptr_t specialization_cid,
+                                      bool sticky,
                                       const Object& owner) {
   const intptr_t kParamCount = RegExpMacroAssembler::kParamCount;
 
   Function& fn =
       Function::Handle(zone, Function::New(Symbols::ColonMatcher(),
                                            RawFunction::kIrregexpFunction,
                                            true,   // Static.
                                            false,  // Not const.
                                            false,  // Not abstract.
                                            false,  // Not external.
@@ skipping 14 matching lines @@
                         Object::dynamic_type());
   fn.SetParameterNameAt(RegExpMacroAssembler::kParamStringIndex,
                         Symbols::string_param());
   fn.SetParameterTypeAt(RegExpMacroAssembler::kParamStartOffsetIndex,
                         Object::dynamic_type());
   fn.SetParameterNameAt(RegExpMacroAssembler::kParamStartOffsetIndex,
                         Symbols::start_index_param());
   fn.set_result_type(Type::Handle(zone, Type::ArrayType()));
 
   // Cache the result.
-  regexp.set_function(specialization_cid, fn);
+  regexp.set_function(specialization_cid, sticky, fn);
 
-  fn.SetRegExpData(regexp, specialization_cid);
+  fn.SetRegExpData(regexp, specialization_cid, sticky);
   fn.set_is_debuggable(false);
 
   // The function is compiled lazily during the first call.
 }
 
 
 RawRegExp* RegExpEngine::CreateRegExp(Thread* thread,
                                       const String& pattern,
                                       bool multi_line,
                                       bool ignore_case) {
@@ skipping 12 matching lines @@
   // TODO(zerny): We might want to use normal string searching algorithms
   // for simple patterns.
   regexp.set_is_complex();
   regexp.set_is_global();  // All dart regexps are global.
 
   if (!FLAG_interpret_irregexp) {
     const Library& lib = Library::Handle(zone, Library::CoreLibrary());
     const Class& owner =
         Class::Handle(zone, lib.LookupClass(Symbols::RegExp()));
 
-    CreateSpecializedFunction(thread, zone, regexp, kOneByteStringCid, owner);
-    CreateSpecializedFunction(thread, zone, regexp, kTwoByteStringCid, owner);
-    CreateSpecializedFunction(thread, zone, regexp, kExternalOneByteStringCid,
-                              owner);
-    CreateSpecializedFunction(thread, zone, regexp, kExternalTwoByteStringCid,
-                              owner);
+    for (intptr_t cid = kOneByteStringCid; cid <= kExternalTwoByteStringCid;
+         cid++) {
+      CreateSpecializedFunction(thread, zone, regexp, cid, /*sticky=*/false,
+                                owner);
+      CreateSpecializedFunction(thread, zone, regexp, cid, /*sticky=*/true,
+                                owner);
+    }
   }
 
   return regexp.raw();
 }
 
 
 }  // namespace dart