[regexp] implement character classes for unicode regexps.

test/cctest/test-regexp.cc

 // Copyright 2012 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 78 matching lines @@
 
 using namespace v8::internal;
 
 
 static bool CheckParse(const char* input) {
   v8::HandleScope scope(CcTest::isolate());
   Zone zone;
   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
   RegExpCompileData result;
   return v8::internal::RegExpParser::ParseRegExp(
-      CcTest::i_isolate(), &zone, &reader, false, false, &result);
+      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result);
 }
 
 
 static void CheckParseEq(const char* input, const char* expected,
                          bool unicode = false) {
   v8::HandleScope scope(CcTest::isolate());
   Zone zone;
   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
   RegExpCompileData result;
-  CHECK(v8::internal::RegExpParser::ParseRegExp(
-      CcTest::i_isolate(), &zone, &reader, false, unicode, &result));
+  JSRegExp::Flags flags = JSRegExp::kNone;
+  if (unicode) flags |= JSRegExp::kUnicode;
+  CHECK(v8::internal::RegExpParser::ParseRegExp(CcTest::i_isolate(), &zone,
+                                                &reader, flags, &result));
   CHECK(result.tree != NULL);
   CHECK(result.error.is_null());
   std::ostringstream os;
   result.tree->Print(os, &zone);
   if (strcmp(expected, os.str().c_str()) != 0) {
     printf("%s | %s\n", expected, os.str().c_str());
   }
   CHECK_EQ(0, strcmp(expected, os.str().c_str()));
 }
 
 
 static bool CheckSimple(const char* input) {
   v8::HandleScope scope(CcTest::isolate());
   Zone zone;
   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
   RegExpCompileData result;
   CHECK(v8::internal::RegExpParser::ParseRegExp(
-      CcTest::i_isolate(), &zone, &reader, false, false, &result));
+      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result));
   CHECK(result.tree != NULL);
   CHECK(result.error.is_null());
   return result.simple;
 }
 
 struct MinMaxPair {
   int min_match;
   int max_match;
 };
 
 
 static MinMaxPair CheckMinMaxMatch(const char* input) {
   v8::HandleScope scope(CcTest::isolate());
   Zone zone;
   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
   RegExpCompileData result;
   CHECK(v8::internal::RegExpParser::ParseRegExp(
-      CcTest::i_isolate(), &zone, &reader, false, false, &result));
+      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result));
   CHECK(result.tree != NULL);
   CHECK(result.error.is_null());
   int min_match = result.tree->min_match();
   int max_match = result.tree->max_match();
   MinMaxPair pair = { min_match, max_match };
   return pair;
 }
 
 
 #define CHECK_PARSE_ERROR(input) CHECK(!CheckParse(input))
@@ skipping 42 matching lines @@
   CheckParseEq("foo(?!bar)baz", "(: 'foo' (-> - 'bar') 'baz')");
   if (lookbehind) {
     CheckParseEq("foo(?<=bar)baz", "(: 'foo' (<- + 'bar') 'baz')");
     CheckParseEq("foo(?<!bar)baz", "(: 'foo' (<- - 'bar') 'baz')");
   } else {
     CHECK_PARSE_ERROR("foo(?<=bar)baz");
     CHECK_PARSE_ERROR("foo(?<!bar)baz");
   }
   CheckParseEq("()", "(^ %)");
   CheckParseEq("(?=)", "(-> + %)");
-  CheckParseEq("[]", "^[\\x00-\\uffff]");  // Doesn't compile on windows
-  CheckParseEq("[^]", "[\\x00-\\uffff]");  // \uffff isn't in codepage 1252
+  CheckParseEq("[]", "^[\\x00-\\u{10ffff}]");  // Doesn't compile on windows
+  CheckParseEq("[^]", "[\\x00-\\u{10ffff}]");  // \uffff isn't in codepage 1252
   CheckParseEq("[x]", "[x]");
   CheckParseEq("[xyz]", "[x y z]");
   CheckParseEq("[a-zA-Z0-9]", "[a-z A-Z 0-9]");
   CheckParseEq("[-123]", "[- 1 2 3]");
   CheckParseEq("[^123]", "^[1 2 3]");
   CheckParseEq("]", "']'");
   CheckParseEq("}", "'}'");
   CheckParseEq("[a-b-c]", "[a-b - c]");
   CheckParseEq("[\\d]", "[0-9]");
   CheckParseEq("[x\\dz]", "[x 0-9 z]");
@@ skipping 88 matching lines @@
 
   // Unicode regexps
   CheckParseEq("\\u{12345}", "'\\ud808\\udf45'", true);
   CheckParseEq("\\u{12345}\\u{23456}", "(! '\\ud808\\udf45' '\\ud84d\\udc56')",
                true);
   CheckParseEq("\\u{12345}|\\u{23456}", "(| '\\ud808\\udf45' '\\ud84d\\udc56')",
                true);
   CheckParseEq("\\u{12345}{3}", "(# 3 3 g '\\ud808\\udf45')", true);
   CheckParseEq("\\u{12345}*", "(# 0 - g '\\ud808\\udf45')", true);
 
+  CheckParseEq("\\ud808\\udf45*", "(# 0 - g '\\ud808\\udf45')", true);
+  CheckParseEq("[\\ud808\\udf45-\\ud809\\udccc]", "[\\u{012345}-\\u{0124cc}]",
+               true);
+
   CHECK_SIMPLE("", false);
   CHECK_SIMPLE("a", true);
   CHECK_SIMPLE("a|b", false);
   CHECK_SIMPLE("a\\n", false);
   CHECK_SIMPLE("^a", false);
   CHECK_SIMPLE("a$", false);
   CHECK_SIMPLE("a\\b!", false);
   CHECK_SIMPLE("a\\Bb", false);
   CHECK_SIMPLE("a*", false);
   CHECK_SIMPLE("a*?", false);
@@ skipping 118 matching lines @@
   CheckParseEq("a|", "(| 'a' %)");
 }
 
 static void ExpectError(const char* input,
                         const char* expected) {
   v8::HandleScope scope(CcTest::isolate());
   Zone zone;
   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
   RegExpCompileData result;
   CHECK(!v8::internal::RegExpParser::ParseRegExp(
-            CcTest::i_isolate(), &zone, &reader, false, false, &result));
+      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result));
   CHECK(result.tree == NULL);
   CHECK(!result.error.is_null());
   v8::base::SmartArrayPointer<char> str = result.error->ToCString(ALLOW_NULLS);
   CHECK_EQ(0, strcmp(expected, str.get()));
 }
 
 
 TEST(Errors) {
   const char* kEndBackslash = "\\ at end of pattern";
   ExpectError("\\", kEndBackslash);
@@ skipping 48 matching lines @@
 static bool NotWord(uc16 c) {
   return !IsRegExpWord(c);
 }
 
 
 static void TestCharacterClassEscapes(uc16 c, bool (pred)(uc16 c)) {
   Zone zone;
   ZoneList<CharacterRange>* ranges =
       new(&zone) ZoneList<CharacterRange>(2, &zone);
   CharacterRange::AddClassEscape(c, ranges, &zone);
-  for (unsigned i = 0; i < (1 << 16); i++) {
+  for (uc32 i = 0; i < (1 << 16); i++) {
     bool in_class = false;
     for (int j = 0; !in_class && j < ranges->length(); j++) {
       CharacterRange& range = ranges->at(j);
       in_class = (range.from() <= i && i <= range.to());
     }
     CHECK_EQ(pred(i), in_class);
   }
 }
 
 
 TEST(CharacterClassEscapes) {
   TestCharacterClassEscapes('.', IsRegExpNewline);
   TestCharacterClassEscapes('d', IsDigit);
   TestCharacterClassEscapes('D', NotDigit);
   TestCharacterClassEscapes('s', IsWhiteSpaceOrLineTerminator);
   TestCharacterClassEscapes('S', NotWhiteSpaceNorLineTermiantor);
   TestCharacterClassEscapes('w', IsRegExpWord);
   TestCharacterClassEscapes('W', NotWord);
 }
 
 
 static RegExpNode* Compile(const char* input, bool multiline, bool unicode,
                            bool is_one_byte, Zone* zone) {
   Isolate* isolate = CcTest::i_isolate();
   FlatStringReader reader(isolate, CStrVector(input));
   RegExpCompileData compile_data;
+  JSRegExp::Flags flags = JSRegExp::kNone;
+  if (multiline) flags = JSRegExp::kMultiline;
+  if (unicode) flags = JSRegExp::kUnicode;
   if (!v8::internal::RegExpParser::ParseRegExp(CcTest::i_isolate(), zone,
-                                               &reader, multiline, unicode,
-                                               &compile_data))
+                                               &reader, flags, &compile_data))
     return NULL;
   Handle<String> pattern = isolate->factory()
                                ->NewStringFromUtf8(CStrVector(input))
                                .ToHandleChecked();
   Handle<String> sample_subject =
       isolate->factory()->NewStringFromUtf8(CStrVector("")).ToHandleChecked();
-  RegExpEngine::Compile(isolate, zone, &compile_data, false, false, multiline,
-                        false, pattern, sample_subject, is_one_byte);
+  RegExpEngine::Compile(isolate, zone, &compile_data, flags, pattern,
+                        sample_subject, is_one_byte);
   return compile_data.node;
 }
 
 
 static void Execute(const char* input, bool multiline, bool unicode,
                     bool is_one_byte, bool dot_output = false) {
   v8::HandleScope scope(CcTest::isolate());
   Zone zone;
   RegExpNode* node = Compile(input, multiline, unicode, is_one_byte, &zone);
   USE(node);
@@ skipping 1088 matching lines @@
   TestSimpleRangeCaseIndependence(isolate, CharacterRange('A' - 1, 'Z' + 1),
                                   CharacterRange('a', 'z'));
   // Here we need to add [l-z] to complete the case independence of
   // [A-Za-z] but we expect [a-z] to be added since we always add a
   // whole block at a time.
   TestSimpleRangeCaseIndependence(isolate, CharacterRange('A', 'k'),
                                   CharacterRange('a', 'z'));
 }
 
 
-static bool InClass(uc16 c, ZoneList<CharacterRange>* ranges) {
+static bool InClass(uc32 c, ZoneList<CharacterRange>* ranges) {
   if (ranges == NULL)
     return false;
   for (int i = 0; i < ranges->length(); i++) {
     CharacterRange range = ranges->at(i);
     if (range.from() <= c && c <= range.to())
       return true;
   }
   return false;
 }
 
 
-TEST(CharClassDifference) {
+TEST(UnicodeRangeSplitter) {
   Zone zone;
   ZoneList<CharacterRange>* base =
       new(&zone) ZoneList<CharacterRange>(1, &zone);
   base->Add(CharacterRange::Everything(), &zone);
-  Vector<const int> overlay = CharacterRange::GetWordBounds();
-  ZoneList<CharacterRange>* included = NULL;
-  ZoneList<CharacterRange>* excluded = NULL;
-  CharacterRange::Split(base, overlay, &included, &excluded, &zone);
-  for (int i = 0; i < (1 << 16); i++) {
-    bool in_base = InClass(i, base);
-    if (in_base) {
-      bool in_overlay = false;
-      for (int j = 0; !in_overlay && j < overlay.length(); j += 2) {
-        if (overlay[j] <= i && i < overlay[j+1])
-          in_overlay = true;
-      }
-      CHECK_EQ(in_overlay, InClass(i, included));
-      CHECK_EQ(!in_overlay, InClass(i, excluded));
-    } else {
-      CHECK(!InClass(i, included));
-      CHECK(!InClass(i, excluded));
-    }
+  UnicodeRangeSplitter splitter(&zone, base);
+  // BMP
+  for (uc32 c = 0; c < 0xd800; c++) {
+    CHECK(InClass(c, splitter.bmp()));
+    CHECK(!InClass(c, splitter.lead_surrogates()));
+    CHECK(!InClass(c, splitter.trail_surrogates()));
+    CHECK(!InClass(c, splitter.non_bmp()));
+  }
+  // Lead surrogates
+  for (uc32 c = 0xd800; c < 0xdbff; c++) {
+    CHECK(!InClass(c, splitter.bmp()));
+    CHECK(InClass(c, splitter.lead_surrogates()));
+    CHECK(!InClass(c, splitter.trail_surrogates()));
+    CHECK(!InClass(c, splitter.non_bmp()));
+  }
+  // Trail surrogates
+  for (uc32 c = 0xdc00; c < 0xdfff; c++) {
+    CHECK(!InClass(c, splitter.bmp()));
+    CHECK(!InClass(c, splitter.lead_surrogates()));
+    CHECK(InClass(c, splitter.trail_surrogates()));
+    CHECK(!InClass(c, splitter.non_bmp()));
+  }
+  // BMP
+  for (uc32 c = 0xe000; c < 0xffff; c++) {
+    CHECK(InClass(c, splitter.bmp()));
+    CHECK(!InClass(c, splitter.lead_surrogates()));
+    CHECK(!InClass(c, splitter.trail_surrogates()));
+    CHECK(!InClass(c, splitter.non_bmp()));
+  }
+  // Non-BMP
+  for (uc32 c = 0x10000; c < 0x10ffff; c++) {
+    CHECK(!InClass(c, splitter.bmp()));
+    CHECK(!InClass(c, splitter.lead_surrogates()));
+    CHECK(!InClass(c, splitter.trail_surrogates()));
+    CHECK(InClass(c, splitter.non_bmp()));
   }
 }
 
 
 TEST(CanonicalizeCharacterSets) {
   Zone zone;
   ZoneList<CharacterRange>* list =
       new(&zone) ZoneList<CharacterRange>(4, &zone);
   CharacterSet set(list);
 
@@ skipping 214 matching lines @@
   // .toString() throws on non-RegExps that aren't RegExp.prototype
   v8::Local<v8::Value> resultToStringError = CompileRun(
       "var exception;"
       "try { RegExp.prototype.toString.call(null) }"
       "catch (e) { exception = e; }"
       "exception");
   CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
   CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeToString]);
   CHECK(resultToStringError->IsObject());
 }