[regexp] implement case-insensitive unicode regexps.

src/regexp/regexp-macro-assembler.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/regexp-macro-assembler.h"
 
 #include "src/assembler.h"
 #include "src/isolate-inl.h"
 #include "src/regexp/regexp-stack.h"
 #include "src/simulator.h"
 
+#ifdef V8_I18N_SUPPORT
+#include "unicode/uchar.h"
+#endif  // V8_I18N_SUPPORT
+
 namespace v8 {
 namespace internal {
 
 RegExpMacroAssembler::RegExpMacroAssembler(Isolate* isolate, Zone* zone)
     : slow_safe_compiler_(false),
       global_mode_(NOT_GLOBAL),
       isolate_(isolate),
       zone_(zone) {}
 
 
 RegExpMacroAssembler::~RegExpMacroAssembler() {
 }
 
 
+int RegExpMacroAssembler::CaseInsensitiveCompareUC16(Address byte_offset1,
+                                                     Address byte_offset2,
+                                                     size_t byte_length,
+                                                     Isolate* isolate) {
+  unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize =
+      isolate->regexp_macro_assembler_canonicalize();
+  // This function is not allowed to cause a garbage collection.
+  // A GC might move the calling generated code and invalidate the
+  // return address on the stack.
+  DCHECK(byte_length % 2 == 0);
+  uc16* substring1 = reinterpret_cast<uc16*>(byte_offset1);
+  uc16* substring2 = reinterpret_cast<uc16*>(byte_offset2);
+  size_t length = byte_length >> 1;
+
+#ifdef V8_I18N_SUPPORT
+  if (isolate == nullptr) {
+    for (size_t i = 0; i < length; i++) {
+      uc32 c1 = substring1[i];
+      uc32 c2 = substring2[i];
+      if (unibrow::Utf16::IsLeadSurrogate(c1)) {

[erikcorry, 2016/01/25 10:26:37]

This looks incomplete wrt unpaired surrogates at the ends of the capture.

[Yang, 2016/01/25 11:46:37]

I think this is correct. Unpaired lead surrogate at the end of the capture would
mean that we exceed |length| when we try to fetch the trail surrogate below. So
the condition on line 51 fails, so we fall through to u_foldCase.
If we have a trail surrogate, there is nothing to combine to anyways.

[erikcorry, 2016/01/25 11:57:47]

I guess we are here making use of the fact that there are no case-equivalency
classes that cross the basic plane boundary?

It would be good to have some test cases that check that we don't allow
/([^]*)[^]*\1/ to match thing like:

".L.LT."
".T.LT."
".LT.L."
".LT.T."

Including variations without the leading or trailing dots.

[Yang, 2016/01/25 12:09:02]

I added a comment about the fact that we rely on Non-BMP to only be case
equivalent to other non-BMP.

But these back reference tests would fail since we do not check whether the back
reference starts/ends in a surrogate pair here.

https://codereview.chromium.org/1601653006/ is supposed to solve this issue, and
I'll add some more tests there.

+        if (!unibrow::Utf16::IsLeadSurrogate(c2)) return 0;
+        if (i + 1 < length) {
+          uc16 c1t = substring1[i + 1];
+          uc16 c2t = substring2[i + 1];
+          if (unibrow::Utf16::IsTrailSurrogate(c1t) &&
+              unibrow::Utf16::IsTrailSurrogate(c2t)) {
+            c1 = unibrow::Utf16::CombineSurrogatePair(c1, c1t);
+            c2 = unibrow::Utf16::CombineSurrogatePair(c2, c2t);
+            i++;
+          }
+        }
+      }
+      c1 = u_foldCase(c1, U_FOLD_CASE_DEFAULT);
+      c2 = u_foldCase(c2, U_FOLD_CASE_DEFAULT);
+      if (c1 != c2) return 0;
+    }
+    return 1;
+  }
+#endif  // V8_I18N_SUPPORT

[erikcorry, 2016/01/25 10:26:37]

Should this be a #else ?

[Yang, 2016/01/25 11:46:37]

No. If we have ICU, we decide on whether to take the unicode path based on
isolate == nullptr. If isolate is not null, we still have to do the non-unicode
thing, which is below.
If we do not have ICU, the only thing we can do is the non-unicode thing.

+  DCHECK_NOT_NULL(isolate);
+  for (size_t i = 0; i < length; i++) {
+    unibrow::uchar c1 = substring1[i];
+    unibrow::uchar c2 = substring2[i];
+    if (c1 != c2) {
+      unibrow::uchar s1[1] = { c1 };
+      canonicalize->get(c1, '\0', s1);
+      if (s1[0] != c2) {
+        unibrow::uchar s2[1] = { c2 };
+        canonicalize->get(c2, '\0', s2);
+        if (s1[0] != s2[0]) {
+          return 0;
+        }
+      }
+    }
+  }
+  return 1;
+}
+
+
 #ifndef V8_INTERPRETED_REGEXP  // Avoid unused code, e.g., on ARM.
 
 NativeRegExpMacroAssembler::NativeRegExpMacroAssembler(Isolate* isolate,
                                                        Zone* zone)
     : RegExpMacroAssembler(isolate, zone) {}
 
 
 NativeRegExpMacroAssembler::~NativeRegExpMacroAssembler() {
 }
 
@@ skipping 202 matching lines @@
     0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
     0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
 
     0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
     0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
     0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
     0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u, 0x00u,
 };
 
 
-int NativeRegExpMacroAssembler::CaseInsensitiveCompareUC16(
-    Address byte_offset1,
-    Address byte_offset2,
-    size_t byte_length,
-    Isolate* isolate) {
-  unibrow::Mapping<unibrow::Ecma262Canonicalize>* canonicalize =
-      isolate->regexp_macro_assembler_canonicalize();
-  // This function is not allowed to cause a garbage collection.
-  // A GC might move the calling generated code and invalidate the
-  // return address on the stack.
-  DCHECK(byte_length % 2 == 0);
-  uc16* substring1 = reinterpret_cast<uc16*>(byte_offset1);
-  uc16* substring2 = reinterpret_cast<uc16*>(byte_offset2);
-  size_t length = byte_length >> 1;
-
-  for (size_t i = 0; i < length; i++) {
-    unibrow::uchar c1 = substring1[i];
-    unibrow::uchar c2 = substring2[i];
-    if (c1 != c2) {
-      unibrow::uchar s1[1] = { c1 };
-      canonicalize->get(c1, '\0', s1);
-      if (s1[0] != c2) {
-        unibrow::uchar s2[1] = { c2 };
-        canonicalize->get(c2, '\0', s2);
-        if (s1[0] != s2[0]) {
-          return 0;
-        }
-      }
-    }
-  }
-  return 1;
-}
-
-
 Address NativeRegExpMacroAssembler::GrowStack(Address stack_pointer,
                                               Address* stack_base,
                                               Isolate* isolate) {
   RegExpStack* regexp_stack = isolate->regexp_stack();
   size_t size = regexp_stack->stack_capacity();
   Address old_stack_base = regexp_stack->stack_base();
   DCHECK(old_stack_base == *stack_base);
   DCHECK(stack_pointer <= old_stack_base);
   DCHECK(static_cast<size_t>(old_stack_base - stack_pointer) <= size);
   Address new_stack_base = regexp_stack->EnsureCapacity(size * 2);
   if (new_stack_base == NULL) {
     return NULL;
   }
   *stack_base = new_stack_base;
   intptr_t stack_content_size = old_stack_base - stack_pointer;
   return new_stack_base - stack_content_size;
 }
 
 #endif  // V8_INTERPRETED_REGEXP
 
 }  // namespace internal
 }  // namespace v8