Reland Extend big-disjunction optimization to case-independent regexps

src/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/v8.h"
 
 #include "src/ast.h"
 #include "src/base/platform/platform.h"
 #include "src/compilation-cache.h"
 #include "src/compiler.h"
@@ skipping 4819 matching lines @@
   RegExpAtom* atom1 = (*a)->AsAtom();
   RegExpAtom* atom2 = (*b)->AsAtom();
   uc16 character1 = atom1->data().at(0);
   uc16 character2 = atom2->data().at(0);
   if (character1 < character2) return -1;
   if (character1 > character2) return 1;
   return 0;
 }
 
 
+static unibrow::uchar Canonical(
+    unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize,
+    unibrow::uchar c) {
+  unibrow::uchar chars[unibrow::Ecma262Canonicalize::kMaxWidth];
+  int length = canonicalize->get(c, '\0', chars);
+  DCHECK_LE(length, 1);
+  unibrow::uchar canonical = c;
+  if (length == 1) canonical = chars[0];
+  return canonical;
+}
+
+
+int CompareFirstCharCaseIndependent(
+    unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize,
+    RegExpTree* const* a, RegExpTree* const* b) {
+  RegExpAtom* atom1 = (*a)->AsAtom();
+  RegExpAtom* atom2 = (*b)->AsAtom();
+  unibrow::uchar character1 = atom1->data().at(0);
+  unibrow::uchar character2 = atom2->data().at(0);
+  if (character1 == character2) return 0;
+  if (character1 >= 'a' || character2 >= 'a') {
+    character1 = Canonical(canonicalize, character1);
+    character2 = Canonical(canonicalize, character2);
+  }
+  return static_cast<int>(character1) - static_cast<int>(character2);
+}
+
+
 // We can stable sort runs of atoms, since the order does not matter if they
 // start with different characters.
 // Returns true if any consecutive atoms were found.
 bool RegExpDisjunction::SortConsecutiveAtoms(RegExpCompiler* compiler) {
   ZoneList<RegExpTree*>* alternatives = this->alternatives();
   int length = alternatives->length();
   bool found_consecutive_atoms = false;
   for (int i = 0; i < length; i++) {
     while (i < length) {
       RegExpTree* alternative = alternatives->at(i);
       if (alternative->IsAtom()) break;
       i++;
     }
     // i is length or it is the index of an atom.
     if (i == length) break;
     int first_atom = i;
     i++;
     while (i < length) {
       RegExpTree* alternative = alternatives->at(i);
       if (!alternative->IsAtom()) break;
       i++;
     }
     // Sort atoms to get ones with common prefixes together.
-    // This step is not valid if we are in a case-independent regexp,
+    // This step is more tricky if we are in a case-independent regexp,
     // because it would change /is|I/ to /I|is/, and order matters when
     // the regexp parts don't match only disjoint starting points. To fix
-    // this would need a version of CompareFirstChar that uses case-
+    // this we have a version of CompareFirstChar that uses case-
     // independent character classes for comparison.
-    if (!compiler->ignore_case()) {
-      DCHECK_LT(first_atom, alternatives->length());
-      DCHECK_LE(i, alternatives->length());
-      DCHECK_LE(first_atom, i);
+    DCHECK_LT(first_atom, alternatives->length());
+    DCHECK_LE(i, alternatives->length());
+    DCHECK_LE(first_atom, i);
+    if (compiler->ignore_case()) {
+      unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize =
+          compiler->isolate()->regexp_macro_assembler_canonicalize();
+      auto compare_closure =
+          [canonicalize](RegExpTree* const* a, RegExpTree* const* b) {
+            return CompareFirstCharCaseIndependent(canonicalize, a, b);
+          };
+      alternatives->StableSort(compare_closure, first_atom, i - first_atom);
+    } else {
       alternatives->StableSort(CompareFirstChar, first_atom, i - first_atom);
     }
     if (i - first_atom > 1) found_consecutive_atoms = true;
   }
   return found_consecutive_atoms;
 }
 
 
 // Optimizes ab|ac|az to a(?:b|c|d).
 void RegExpDisjunction::RationalizeConsecutiveAtoms(RegExpCompiler* compiler) {
   Zone* zone = compiler->zone();
   ZoneList<RegExpTree*>* alternatives = this->alternatives();
   int length = alternatives->length();
 
   int write_posn = 0;
   int i = 0;
   while (i < length) {
     RegExpTree* alternative = alternatives->at(i);
     if (!alternative->IsAtom()) {
       alternatives->at(write_posn++) = alternatives->at(i);
       i++;
       continue;
     }
     RegExpAtom* atom = alternative->AsAtom();
-    uc16 common_prefix = atom->data().at(0);
+    unibrow::uchar common_prefix = atom->data().at(0);
     int first_with_prefix = i;
     int prefix_length = atom->length();
     i++;
     while (i < length) {
       alternative = alternatives->at(i);
       if (!alternative->IsAtom()) break;
       atom = alternative->AsAtom();
-      if (atom->data().at(0) != common_prefix) break;
+      unibrow::uchar new_prefix = atom->data().at(0);
+      if (new_prefix != common_prefix) {
+        if (!compiler->ignore_case()) break;
+        unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize =
+            compiler->isolate()->regexp_macro_assembler_canonicalize();
+        new_prefix = Canonical(canonicalize, new_prefix);
+        common_prefix = Canonical(canonicalize, common_prefix);
+        if (new_prefix != common_prefix) break;
+      }
       prefix_length = Min(prefix_length, atom->length());
       i++;
     }
     if (i > first_with_prefix + 2) {
       // Found worthwhile run of alternatives with common prefix of at least one
       // character.  The sorting function above did not sort on more than one
       // character for reasons of correctness, but there may still be a longer
       // common prefix if the terms were similar or presorted in the input.
       // Find out how long the common prefix is.
       int run_length = i - first_with_prefix;
       atom = alternatives->at(first_with_prefix)->AsAtom();
       for (int j = 1; j < run_length && prefix_length > 1; j++) {
         RegExpAtom* old_atom =
             alternatives->at(j + first_with_prefix)->AsAtom();
         for (int k = 1; k < prefix_length; k++) {
-          if (atom->data().at(k) != old_atom->data().at(k)) prefix_length = k;
+          if (atom->data().at(k) != old_atom->data().at(k)) {
+            prefix_length = k;
+            break;
+          }
         }
       }
       RegExpAtom* prefix =
           new (zone) RegExpAtom(atom->data().SubVector(0, prefix_length));
       ZoneList<RegExpTree*>* pair = new (zone) ZoneList<RegExpTree*>(2, zone);
       pair->Add(prefix, zone);
       ZoneList<RegExpTree*>* suffixes =
           new (zone) ZoneList<RegExpTree*>(run_length, zone);
       for (int j = 0; j < run_length; j++) {
         RegExpAtom* old_atom =
@@ skipping 1424 matching lines @@
   bool too_much = pattern->length() > RegExpImpl::kRegExpTooLargeToOptimize;
   if (heap->total_regexp_code_generated() > RegExpImpl::kRegExpCompiledLimit &&
       heap->isolate()->memory_allocator()->SizeExecutable() >
           RegExpImpl::kRegExpExecutableMemoryLimit) {
     too_much = true;
   }
   return too_much;
 }
 }  // namespace internal
 }  // namespace v8