src/v8/test/cctest/test-regexp.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28
  29 #include <stdlib.h>
  30
  31 #include "v8.h"
  32
  33 #include "ast.h"
  34 #include "char-predicates-inl.h"
  35 #include "cctest.h"
  36 #include "jsregexp.h"
  37 #include "parser.h"
  38 #include "regexp-macro-assembler.h"
  39 #include "regexp-macro-assembler-irregexp.h"
  40 #include "string-stream.h"
  41 #include "zone-inl.h"
  42 #ifdef V8_INTERPRETED_REGEXP
  43 #include "interpreter-irregexp.h"
  44 #else  // V8_INTERPRETED_REGEXP
  45 #include "macro-assembler.h"
  46 #include "code.h"
  47 #if V8_TARGET_ARCH_ARM
  48 #include "arm/assembler-arm.h"
  49 #include "arm/macro-assembler-arm.h"
  50 #include "arm/regexp-macro-assembler-arm.h"
  51 #endif
  52 #if V8_TARGET_ARCH_ARM64
  53 #include "arm64/assembler-arm64.h"
  54 #include "arm64/macro-assembler-arm64.h"
  55 #include "arm64/regexp-macro-assembler-arm64.h"
  56 #endif
  57 #if V8_TARGET_ARCH_MIPS
  58 #include "mips/assembler-mips.h"
  59 #include "mips/macro-assembler-mips.h"
  60 #include "mips/regexp-macro-assembler-mips.h"
  61 #endif
  62 #if V8_TARGET_ARCH_X64
  63 #include "x64/assembler-x64.h"
  64 #include "x64/macro-assembler-x64.h"
  65 #include "x64/regexp-macro-assembler-x64.h"
  66 #endif
  67 #if V8_TARGET_ARCH_IA32
  68 #include "ia32/assembler-ia32.h"
  69 #include "ia32/macro-assembler-ia32.h"
  70 #include "ia32/regexp-macro-assembler-ia32.h"
  71 #endif
  72 #endif  // V8_INTERPRETED_REGEXP
  73
  74 using namespace v8::internal;
  75
  76
  77 static bool CheckParse(const char* input) {
  78   V8::Initialize(NULL);
  79   v8::HandleScope scope(CcTest::isolate());
  80   Zone zone(CcTest::i_isolate());
  81   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
  82   RegExpCompileData result;
  83   return v8::internal::RegExpParser::ParseRegExp(
  84       &reader, false, &result, &zone);
  85 }
  86
  87
  88 static SmartArrayPointer<const char> Parse(const char* input) {
  89   V8::Initialize(NULL);
  90   v8::HandleScope scope(CcTest::isolate());
  91   Zone zone(CcTest::i_isolate());
  92   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
  93   RegExpCompileData result;
  94   CHECK(v8::internal::RegExpParser::ParseRegExp(
  95       &reader, false, &result, &zone));
  96   CHECK(result.tree != NULL);
  97   CHECK(result.error.is_null());
  98   SmartArrayPointer<const char> output = result.tree->ToString(&zone);
  99   return output;
 100 }
 101
 102
 103 static bool CheckSimple(const char* input) {
 104   V8::Initialize(NULL);
 105   v8::HandleScope scope(CcTest::isolate());
 106   Zone zone(CcTest::i_isolate());
 107   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
 108   RegExpCompileData result;
 109   CHECK(v8::internal::RegExpParser::ParseRegExp(
 110       &reader, false, &result, &zone));
 111   CHECK(result.tree != NULL);
 112   CHECK(result.error.is_null());
 113   return result.simple;
 114 }
 115
 116 struct MinMaxPair {
 117   int min_match;
 118   int max_match;
 119 };
 120
 121
 122 static MinMaxPair CheckMinMaxMatch(const char* input) {
 123   V8::Initialize(NULL);
 124   v8::HandleScope scope(CcTest::isolate());
 125   Zone zone(CcTest::i_isolate());
 126   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
 127   RegExpCompileData result;
 128   CHECK(v8::internal::RegExpParser::ParseRegExp(
 129       &reader, false, &result, &zone));
 130   CHECK(result.tree != NULL);
 131   CHECK(result.error.is_null());
 132   int min_match = result.tree->min_match();
 133   int max_match = result.tree->max_match();
 134   MinMaxPair pair = { min_match, max_match };
 135   return pair;
 136 }
 137
 138
 139 #define CHECK_PARSE_ERROR(input) CHECK(!CheckParse(input))
 140 #define CHECK_PARSE_EQ(input, expected) CHECK_EQ(expected, Parse(input).get())
 141 #define CHECK_SIMPLE(input, simple) CHECK_EQ(simple, CheckSimple(input));
 142 #define CHECK_MIN_MAX(input, min, max)                                         \
 143   { MinMaxPair min_max = CheckMinMaxMatch(input);                              \
 144     CHECK_EQ(min, min_max.min_match);                                          \
 145     CHECK_EQ(max, min_max.max_match);                                          \
 146   }
 147
 148 TEST(Parser) {
 149   V8::Initialize(NULL);
 150
 151   CHECK_PARSE_ERROR("?");
 152
 153   CHECK_PARSE_EQ("abc", "'abc'");
 154   CHECK_PARSE_EQ("", "%");
 155   CHECK_PARSE_EQ("abc|def", "(| 'abc' 'def')");
 156   CHECK_PARSE_EQ("abc|def|ghi", "(| 'abc' 'def' 'ghi')");
 157   CHECK_PARSE_EQ("^xxx$", "(: @^i 'xxx' @$i)");
 158   CHECK_PARSE_EQ("ab\\b\\d\\bcd", "(: 'ab' @b [0-9] @b 'cd')");
 159   CHECK_PARSE_EQ("\\w|\\d", "(| [0-9 A-Z _ a-z] [0-9])");
 160   CHECK_PARSE_EQ("a*", "(# 0 - g 'a')");
 161   CHECK_PARSE_EQ("a*?", "(# 0 - n 'a')");
 162   CHECK_PARSE_EQ("abc+", "(: 'ab' (# 1 - g 'c'))");
 163   CHECK_PARSE_EQ("abc+?", "(: 'ab' (# 1 - n 'c'))");
 164   CHECK_PARSE_EQ("xyz?", "(: 'xy' (# 0 1 g 'z'))");
 165   CHECK_PARSE_EQ("xyz??", "(: 'xy' (# 0 1 n 'z'))");
 166   CHECK_PARSE_EQ("xyz{0,1}", "(: 'xy' (# 0 1 g 'z'))");
 167   CHECK_PARSE_EQ("xyz{0,1}?", "(: 'xy' (# 0 1 n 'z'))");
 168   CHECK_PARSE_EQ("xyz{93}", "(: 'xy' (# 93 93 g 'z'))");
 169   CHECK_PARSE_EQ("xyz{93}?", "(: 'xy' (# 93 93 n 'z'))");
 170   CHECK_PARSE_EQ("xyz{1,32}", "(: 'xy' (# 1 32 g 'z'))");
 171   CHECK_PARSE_EQ("xyz{1,32}?", "(: 'xy' (# 1 32 n 'z'))");
 172   CHECK_PARSE_EQ("xyz{1,}", "(: 'xy' (# 1 - g 'z'))");
 173   CHECK_PARSE_EQ("xyz{1,}?", "(: 'xy' (# 1 - n 'z'))");
 174   CHECK_PARSE_EQ("a\\fb\\nc\\rd\\te\\vf", "'a\\x0cb\\x0ac\\x0dd\\x09e\\x0bf'");
 175   CHECK_PARSE_EQ("a\\nb\\bc", "(: 'a\\x0ab' @b 'c')");
 176   CHECK_PARSE_EQ("(?:foo)", "'foo'");
 177   CHECK_PARSE_EQ("(?: foo )", "' foo '");
 178   CHECK_PARSE_EQ("(foo|bar|baz)", "(^ (| 'foo' 'bar' 'baz'))");
 179   CHECK_PARSE_EQ("foo|(bar|baz)|quux", "(| 'foo' (^ (| 'bar' 'baz')) 'quux')");
 180   CHECK_PARSE_EQ("foo(?=bar)baz", "(: 'foo' (-> + 'bar') 'baz')");
 181   CHECK_PARSE_EQ("foo(?!bar)baz", "(: 'foo' (-> - 'bar') 'baz')");
 182   CHECK_PARSE_EQ("()", "(^ %)");
 183   CHECK_PARSE_EQ("(?=)", "(-> + %)");
 184   CHECK_PARSE_EQ("[]", "^[\\x00-\\uffff]");   // Doesn't compile on windows
 185   CHECK_PARSE_EQ("[^]", "[\\x00-\\uffff]");   // \uffff isn't in codepage 1252
 186   CHECK_PARSE_EQ("[x]", "[x]");
 187   CHECK_PARSE_EQ("[xyz]", "[x y z]");
 188   CHECK_PARSE_EQ("[a-zA-Z0-9]", "[a-z A-Z 0-9]");
 189   CHECK_PARSE_EQ("[-123]", "[- 1 2 3]");
 190   CHECK_PARSE_EQ("[^123]", "^[1 2 3]");
 191   CHECK_PARSE_EQ("]", "']'");
 192   CHECK_PARSE_EQ("}", "'}'");
 193   CHECK_PARSE_EQ("[a-b-c]", "[a-b - c]");
 194   CHECK_PARSE_EQ("[\\d]", "[0-9]");
 195   CHECK_PARSE_EQ("[x\\dz]", "[x 0-9 z]");
 196   CHECK_PARSE_EQ("[\\d-z]", "[0-9 - z]");
 197   CHECK_PARSE_EQ("[\\d-\\d]", "[0-9 - 0-9]");
 198   CHECK_PARSE_EQ("[z-\\d]", "[z - 0-9]");
 199   // Control character outside character class.
 200   CHECK_PARSE_EQ("\\cj\\cJ\\ci\\cI\\ck\\cK",
 201                  "'\\x0a\\x0a\\x09\\x09\\x0b\\x0b'");
 202   CHECK_PARSE_EQ("\\c!", "'\\c!'");
 203   CHECK_PARSE_EQ("\\c_", "'\\c_'");
 204   CHECK_PARSE_EQ("\\c~", "'\\c~'");
 205   CHECK_PARSE_EQ("\\c1", "'\\c1'");
 206   // Control character inside character class.
 207   CHECK_PARSE_EQ("[\\c!]", "[\\ c !]");
 208   CHECK_PARSE_EQ("[\\c_]", "[\\x1f]");
 209   CHECK_PARSE_EQ("[\\c~]", "[\\ c ~]");
 210   CHECK_PARSE_EQ("[\\ca]", "[\\x01]");
 211   CHECK_PARSE_EQ("[\\cz]", "[\\x1a]");
 212   CHECK_PARSE_EQ("[\\cA]", "[\\x01]");
 213   CHECK_PARSE_EQ("[\\cZ]", "[\\x1a]");
 214   CHECK_PARSE_EQ("[\\c1]", "[\\x11]");
 215
 216   CHECK_PARSE_EQ("[a\\]c]", "[a ] c]");
 217   CHECK_PARSE_EQ("\\[\\]\\{\\}\\(\\)\\%\\^\\#\\ ", "'[]{}()%^# '");
 218   CHECK_PARSE_EQ("[\\[\\]\\{\\}\\(\\)\\%\\^\\#\\ ]", "[[ ] { } ( ) % ^ #  ]");
 219   CHECK_PARSE_EQ("\\0", "'\\x00'");
 220   CHECK_PARSE_EQ("\\8", "'8'");
 221   CHECK_PARSE_EQ("\\9", "'9'");
 222   CHECK_PARSE_EQ("\\11", "'\\x09'");
 223   CHECK_PARSE_EQ("\\11a", "'\\x09a'");
 224   CHECK_PARSE_EQ("\\011", "'\\x09'");
 225   CHECK_PARSE_EQ("\\00011", "'\\x0011'");
 226   CHECK_PARSE_EQ("\\118", "'\\x098'");
 227   CHECK_PARSE_EQ("\\111", "'I'");
 228   CHECK_PARSE_EQ("\\1111", "'I1'");
 229   CHECK_PARSE_EQ("(x)(x)(x)\\1", "(: (^ 'x') (^ 'x') (^ 'x') (<- 1))");
 230   CHECK_PARSE_EQ("(x)(x)(x)\\2", "(: (^ 'x') (^ 'x') (^ 'x') (<- 2))");
 231   CHECK_PARSE_EQ("(x)(x)(x)\\3", "(: (^ 'x') (^ 'x') (^ 'x') (<- 3))");
 232   CHECK_PARSE_EQ("(x)(x)(x)\\4", "(: (^ 'x') (^ 'x') (^ 'x') '\\x04')");
 233   CHECK_PARSE_EQ("(x)(x)(x)\\1*", "(: (^ 'x') (^ 'x') (^ 'x')"
 234                                " (# 0 - g (<- 1)))");
 235   CHECK_PARSE_EQ("(x)(x)(x)\\2*", "(: (^ 'x') (^ 'x') (^ 'x')"
 236                                " (# 0 - g (<- 2)))");
 237   CHECK_PARSE_EQ("(x)(x)(x)\\3*", "(: (^ 'x') (^ 'x') (^ 'x')"
 238                                " (# 0 - g (<- 3)))");
 239   CHECK_PARSE_EQ("(x)(x)(x)\\4*", "(: (^ 'x') (^ 'x') (^ 'x')"
 240                                " (# 0 - g '\\x04'))");
 241   CHECK_PARSE_EQ("(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)\\10",
 242               "(: (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x')"
 243               " (^ 'x') (^ 'x') (^ 'x') (^ 'x') (<- 10))");
 244   CHECK_PARSE_EQ("(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)\\11",
 245               "(: (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x')"
 246               " (^ 'x') (^ 'x') (^ 'x') (^ 'x') '\\x09')");
 247   CHECK_PARSE_EQ("(a)\\1", "(: (^ 'a') (<- 1))");
 248   CHECK_PARSE_EQ("(a\\1)", "(^ 'a')");
 249   CHECK_PARSE_EQ("(\\1a)", "(^ 'a')");
 250   CHECK_PARSE_EQ("(?=a)?a", "'a'");
 251   CHECK_PARSE_EQ("(?=a){0,10}a", "'a'");
 252   CHECK_PARSE_EQ("(?=a){1,10}a", "(: (-> + 'a') 'a')");
 253   CHECK_PARSE_EQ("(?=a){9,10}a", "(: (-> + 'a') 'a')");
 254   CHECK_PARSE_EQ("(?!a)?a", "'a'");
 255   CHECK_PARSE_EQ("\\1(a)", "(^ 'a')");
 256   CHECK_PARSE_EQ("(?!(a))\\1", "(: (-> - (^ 'a')) (<- 1))");
 257   CHECK_PARSE_EQ("(?!\\1(a\\1)\\1)\\1", "(: (-> - (: (^ 'a') (<- 1))) (<- 1))");
 258   CHECK_PARSE_EQ("[\\0]", "[\\x00]");
 259   CHECK_PARSE_EQ("[\\11]", "[\\x09]");
 260   CHECK_PARSE_EQ("[\\11a]", "[\\x09 a]");
 261   CHECK_PARSE_EQ("[\\011]", "[\\x09]");
 262   CHECK_PARSE_EQ("[\\00011]", "[\\x00 1 1]");
 263   CHECK_PARSE_EQ("[\\118]", "[\\x09 8]");
 264   CHECK_PARSE_EQ("[\\111]", "[I]");
 265   CHECK_PARSE_EQ("[\\1111]", "[I 1]");
 266   CHECK_PARSE_EQ("\\x34", "'\x34'");
 267   CHECK_PARSE_EQ("\\x60", "'\x60'");
 268   CHECK_PARSE_EQ("\\x3z", "'x3z'");
 269   CHECK_PARSE_EQ("\\c", "'\\c'");
 270   CHECK_PARSE_EQ("\\u0034", "'\x34'");
 271   CHECK_PARSE_EQ("\\u003z", "'u003z'");
 272   CHECK_PARSE_EQ("foo[z]*", "(: 'foo' (# 0 - g [z]))");
 273
 274   CHECK_SIMPLE("", false);
 275   CHECK_SIMPLE("a", true);
 276   CHECK_SIMPLE("a|b", false);
 277   CHECK_SIMPLE("a\\n", false);
 278   CHECK_SIMPLE("^a", false);
 279   CHECK_SIMPLE("a$", false);
 280   CHECK_SIMPLE("a\\b!", false);
 281   CHECK_SIMPLE("a\\Bb", false);
 282   CHECK_SIMPLE("a*", false);
 283   CHECK_SIMPLE("a*?", false);
 284   CHECK_SIMPLE("a?", false);
 285   CHECK_SIMPLE("a??", false);
 286   CHECK_SIMPLE("a{0,1}?", false);
 287   CHECK_SIMPLE("a{1,1}?", false);
 288   CHECK_SIMPLE("a{1,2}?", false);
 289   CHECK_SIMPLE("a+?", false);
 290   CHECK_SIMPLE("(a)", false);
 291   CHECK_SIMPLE("(a)\\1", false);
 292   CHECK_SIMPLE("(\\1a)", false);
 293   CHECK_SIMPLE("\\1(a)", false);
 294   CHECK_SIMPLE("a\\s", false);
 295   CHECK_SIMPLE("a\\S", false);
 296   CHECK_SIMPLE("a\\d", false);
 297   CHECK_SIMPLE("a\\D", false);
 298   CHECK_SIMPLE("a\\w", false);
 299   CHECK_SIMPLE("a\\W", false);
 300   CHECK_SIMPLE("a.", false);
 301   CHECK_SIMPLE("a\\q", false);
 302   CHECK_SIMPLE("a[a]", false);
 303   CHECK_SIMPLE("a[^a]", false);
 304   CHECK_SIMPLE("a[a-z]", false);
 305   CHECK_SIMPLE("a[\\q]", false);
 306   CHECK_SIMPLE("a(?:b)", false);
 307   CHECK_SIMPLE("a(?=b)", false);
 308   CHECK_SIMPLE("a(?!b)", false);
 309   CHECK_SIMPLE("\\x60", false);
 310   CHECK_SIMPLE("\\u0060", false);
 311   CHECK_SIMPLE("\\cA", false);
 312   CHECK_SIMPLE("\\q", false);
 313   CHECK_SIMPLE("\\1112", false);
 314   CHECK_SIMPLE("\\0", false);
 315   CHECK_SIMPLE("(a)\\1", false);
 316   CHECK_SIMPLE("(?=a)?a", false);
 317   CHECK_SIMPLE("(?!a)?a\\1", false);
 318   CHECK_SIMPLE("(?:(?=a))a\\1", false);
 319
 320   CHECK_PARSE_EQ("a{}", "'a{}'");
 321   CHECK_PARSE_EQ("a{,}", "'a{,}'");
 322   CHECK_PARSE_EQ("a{", "'a{'");
 323   CHECK_PARSE_EQ("a{z}", "'a{z}'");
 324   CHECK_PARSE_EQ("a{1z}", "'a{1z}'");
 325   CHECK_PARSE_EQ("a{12z}", "'a{12z}'");
 326   CHECK_PARSE_EQ("a{12,", "'a{12,'");
 327   CHECK_PARSE_EQ("a{12,3b", "'a{12,3b'");
 328   CHECK_PARSE_EQ("{}", "'{}'");
 329   CHECK_PARSE_EQ("{,}", "'{,}'");
 330   CHECK_PARSE_EQ("{", "'{'");
 331   CHECK_PARSE_EQ("{z}", "'{z}'");
 332   CHECK_PARSE_EQ("{1z}", "'{1z}'");
 333   CHECK_PARSE_EQ("{12z}", "'{12z}'");
 334   CHECK_PARSE_EQ("{12,", "'{12,'");
 335   CHECK_PARSE_EQ("{12,3b", "'{12,3b'");
 336
 337   CHECK_MIN_MAX("a", 1, 1);
 338   CHECK_MIN_MAX("abc", 3, 3);
 339   CHECK_MIN_MAX("a[bc]d", 3, 3);
 340   CHECK_MIN_MAX("a|bc", 1, 2);
 341   CHECK_MIN_MAX("ab|c", 1, 2);
 342   CHECK_MIN_MAX("a||bc", 0, 2);
 343   CHECK_MIN_MAX("|", 0, 0);
 344   CHECK_MIN_MAX("(?:ab)", 2, 2);
 345   CHECK_MIN_MAX("(?:ab|cde)", 2, 3);
 346   CHECK_MIN_MAX("(?:ab)|cde", 2, 3);
 347   CHECK_MIN_MAX("(ab)", 2, 2);
 348   CHECK_MIN_MAX("(ab|cde)", 2, 3);
 349   CHECK_MIN_MAX("(ab)\\1", 2, 4);
 350   CHECK_MIN_MAX("(ab|cde)\\1", 2, 6);
 351   CHECK_MIN_MAX("(?:ab)?", 0, 2);
 352   CHECK_MIN_MAX("(?:ab)*", 0, RegExpTree::kInfinity);
 353   CHECK_MIN_MAX("(?:ab)+", 2, RegExpTree::kInfinity);
 354   CHECK_MIN_MAX("a?", 0, 1);
 355   CHECK_MIN_MAX("a*", 0, RegExpTree::kInfinity);
 356   CHECK_MIN_MAX("a+", 1, RegExpTree::kInfinity);
 357   CHECK_MIN_MAX("a??", 0, 1);
 358   CHECK_MIN_MAX("a*?", 0, RegExpTree::kInfinity);
 359   CHECK_MIN_MAX("a+?", 1, RegExpTree::kInfinity);
 360   CHECK_MIN_MAX("(?:a?)?", 0, 1);
 361   CHECK_MIN_MAX("(?:a*)?", 0, RegExpTree::kInfinity);
 362   CHECK_MIN_MAX("(?:a+)?", 0, RegExpTree::kInfinity);
 363   CHECK_MIN_MAX("(?:a?)+", 0, RegExpTree::kInfinity);
 364   CHECK_MIN_MAX("(?:a*)+", 0, RegExpTree::kInfinity);
 365   CHECK_MIN_MAX("(?:a+)+", 1, RegExpTree::kInfinity);
 366   CHECK_MIN_MAX("(?:a?)*", 0, RegExpTree::kInfinity);
 367   CHECK_MIN_MAX("(?:a*)*", 0, RegExpTree::kInfinity);
 368   CHECK_MIN_MAX("(?:a+)*", 0, RegExpTree::kInfinity);
 369   CHECK_MIN_MAX("a{0}", 0, 0);
 370   CHECK_MIN_MAX("(?:a+){0}", 0, 0);
 371   CHECK_MIN_MAX("(?:a+){0,0}", 0, 0);
 372   CHECK_MIN_MAX("a*b", 1, RegExpTree::kInfinity);
 373   CHECK_MIN_MAX("a+b", 2, RegExpTree::kInfinity);
 374   CHECK_MIN_MAX("a*b|c", 1, RegExpTree::kInfinity);
 375   CHECK_MIN_MAX("a+b|c", 1, RegExpTree::kInfinity);
 376   CHECK_MIN_MAX("(?:a{5,1000000}){3,1000000}", 15, RegExpTree::kInfinity);
 377   CHECK_MIN_MAX("(?:ab){4,7}", 8, 14);
 378   CHECK_MIN_MAX("a\\bc", 2, 2);
 379   CHECK_MIN_MAX("a\\Bc", 2, 2);
 380   CHECK_MIN_MAX("a\\sc", 3, 3);
 381   CHECK_MIN_MAX("a\\Sc", 3, 3);
 382   CHECK_MIN_MAX("a(?=b)c", 2, 2);
 383   CHECK_MIN_MAX("a(?=bbb|bb)c", 2, 2);
 384   CHECK_MIN_MAX("a(?!bbb|bb)c", 2, 2);
 385 }
 386
 387
 388 TEST(ParserRegression) {
 389   CHECK_PARSE_EQ("[A-Z$-][x]", "(! [A-Z $ -] [x])");
 390   CHECK_PARSE_EQ("a{3,4*}", "(: 'a{3,' (# 0 - g '4') '}')");
 391   CHECK_PARSE_EQ("{", "'{'");
 392   CHECK_PARSE_EQ("a|", "(| 'a' %)");
 393 }
 394
 395 static void ExpectError(const char* input,
 396                         const char* expected) {
 397   V8::Initialize(NULL);
 398   v8::HandleScope scope(CcTest::isolate());
 399   Zone zone(CcTest::i_isolate());
 400   FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
 401   RegExpCompileData result;
 402   CHECK(!v8::internal::RegExpParser::ParseRegExp(
 403       &reader, false, &result, &zone));
 404   CHECK(result.tree == NULL);
 405   CHECK(!result.error.is_null());
 406   SmartArrayPointer<char> str = result.error->ToCString(ALLOW_NULLS);
 407   CHECK_EQ(expected, str.get());
 408 }
 409
 410
 411 TEST(Errors) {
 412   const char* kEndBackslash = "\\ at end of pattern";
 413   ExpectError("\\", kEndBackslash);
 414   const char* kUnterminatedGroup = "Unterminated group";
 415   ExpectError("(foo", kUnterminatedGroup);
 416   const char* kInvalidGroup = "Invalid group";
 417   ExpectError("(?", kInvalidGroup);
 418   const char* kUnterminatedCharacterClass = "Unterminated character class";
 419   ExpectError("[", kUnterminatedCharacterClass);
 420   ExpectError("[a-", kUnterminatedCharacterClass);
 421   const char* kNothingToRepeat = "Nothing to repeat";
 422   ExpectError("*", kNothingToRepeat);
 423   ExpectError("?", kNothingToRepeat);
 424   ExpectError("+", kNothingToRepeat);
 425   ExpectError("{1}", kNothingToRepeat);
 426   ExpectError("{1,2}", kNothingToRepeat);
 427   ExpectError("{1,}", kNothingToRepeat);
 428
 429   // Check that we don't allow more than kMaxCapture captures
 430   const int kMaxCaptures = 1 << 16;  // Must match RegExpParser::kMaxCaptures.
 431   const char* kTooManyCaptures = "Too many captures";
 432   HeapStringAllocator allocator;
 433   StringStream accumulator(&allocator);
 434   for (int i = 0; i <= kMaxCaptures; i++) {
 435     accumulator.Add("()");
 436   }
 437   SmartArrayPointer<const char> many_captures(accumulator.ToCString());
 438   ExpectError(many_captures.get(), kTooManyCaptures);
 439 }
 440
 441
 442 static bool IsDigit(uc16 c) {
 443   return ('0' <= c && c <= '9');
 444 }
 445
 446
 447 static bool NotDigit(uc16 c) {
 448   return !IsDigit(c);
 449 }
 450
 451
 452 static bool IsWhiteSpaceOrLineTerminator(uc16 c) {
 453   // According to ECMA 5.1, 15.10.2.12 the CharacterClassEscape \s includes
 454   // WhiteSpace (7.2) and LineTerminator (7.3) values.
 455   return v8::internal::WhiteSpaceOrLineTerminator::Is(c);
 456 }
 457
 458
 459 static bool NotWhiteSpaceNorLineTermiantor(uc16 c) {
 460   return !IsWhiteSpaceOrLineTerminator(c);
 461 }
 462
 463
 464 static bool NotWord(uc16 c) {
 465   return !IsRegExpWord(c);
 466 }
 467
 468
 469 static void TestCharacterClassEscapes(uc16 c, bool (pred)(uc16 c)) {
 470   Zone zone(CcTest::i_isolate());
 471   ZoneList<CharacterRange>* ranges =
 472       new(&zone) ZoneList<CharacterRange>(2, &zone);
 473   CharacterRange::AddClassEscape(c, ranges, &zone);
 474   for (unsigned i = 0; i < (1 << 16); i++) {
 475     bool in_class = false;
 476     for (int j = 0; !in_class && j < ranges->length(); j++) {
 477       CharacterRange& range = ranges->at(j);
 478       in_class = (range.from() <= i && i <= range.to());
 479     }
 480     CHECK_EQ(pred(i), in_class);
 481   }
 482 }
 483
 484
 485 TEST(CharacterClassEscapes) {
 486   v8::internal::V8::Initialize(NULL);
 487   TestCharacterClassEscapes('.', IsRegExpNewline);
 488   TestCharacterClassEscapes('d', IsDigit);
 489   TestCharacterClassEscapes('D', NotDigit);
 490   TestCharacterClassEscapes('s', IsWhiteSpaceOrLineTerminator);
 491   TestCharacterClassEscapes('S', NotWhiteSpaceNorLineTermiantor);
 492   TestCharacterClassEscapes('w', IsRegExpWord);
 493   TestCharacterClassEscapes('W', NotWord);
 494 }
 495
 496
 497 static RegExpNode* Compile(const char* input,
 498                            bool multiline,
 499                            bool is_ascii,
 500                            Zone* zone) {
 501   V8::Initialize(NULL);
 502   Isolate* isolate = CcTest::i_isolate();
 503   FlatStringReader reader(isolate, CStrVector(input));
 504   RegExpCompileData compile_data;
 505   if (!v8::internal::RegExpParser::ParseRegExp(&reader, multiline,
 506                                                &compile_data, zone))
 507     return NULL;
 508   Handle<String> pattern = isolate->factory()->
 509       NewStringFromUtf8(CStrVector(input)).ToHandleChecked();
 510   Handle<String> sample_subject =
 511       isolate->factory()->NewStringFromUtf8(CStrVector("")).ToHandleChecked();
 512   RegExpEngine::Compile(&compile_data,
 513                         false,
 514                         false,
 515                         multiline,
 516                         pattern,
 517                         sample_subject,
 518                         is_ascii,
 519                         zone);
 520   return compile_data.node;
 521 }
 522
 523
 524 static void Execute(const char* input,
 525                     bool multiline,
 526                     bool is_ascii,
 527                     bool dot_output = false) {
 528   v8::HandleScope scope(CcTest::isolate());
 529   Zone zone(CcTest::i_isolate());
 530   RegExpNode* node = Compile(input, multiline, is_ascii, &zone);
 531   USE(node);
 532 #ifdef DEBUG
 533   if (dot_output) {
 534     RegExpEngine::DotPrint(input, node, false);
 535   }
 536 #endif  // DEBUG
 537 }
 538
 539
 540 class TestConfig {
 541  public:
 542   typedef int Key;
 543   typedef int Value;
 544   static const int kNoKey;
 545   static int NoValue() { return 0; }
 546   static inline int Compare(int a, int b) {
 547     if (a < b)
 548       return -1;
 549     else if (a > b)
 550       return 1;
 551     else
 552       return 0;
 553   }
 554 };
 555
 556
 557 const int TestConfig::kNoKey = 0;
 558
 559
 560 static unsigned PseudoRandom(int i, int j) {
 561   return ~(~((i * 781) ^ (j * 329)));
 562 }
 563
 564
 565 TEST(SplayTreeSimple) {
 566   v8::internal::V8::Initialize(NULL);
 567   static const unsigned kLimit = 1000;
 568   Zone zone(CcTest::i_isolate());
 569   ZoneSplayTree<TestConfig> tree(&zone);
 570   bool seen[kLimit];
 571   for (unsigned i = 0; i < kLimit; i++) seen[i] = false;
 572 #define CHECK_MAPS_EQUAL() do {                                      \
 573     for (unsigned k = 0; k < kLimit; k++)                            \
 574       CHECK_EQ(seen[k], tree.Find(k, &loc));                         \
 575   } while (false)
 576   for (int i = 0; i < 50; i++) {
 577     for (int j = 0; j < 50; j++) {
 578       unsigned next = PseudoRandom(i, j) % kLimit;
 579       if (seen[next]) {
 580         // We've already seen this one.  Check the value and remove
 581         // it.
 582         ZoneSplayTree<TestConfig>::Locator loc;
 583         CHECK(tree.Find(next, &loc));
 584         CHECK_EQ(next, loc.key());
 585         CHECK_EQ(3 * next, loc.value());
 586         tree.Remove(next);
 587         seen[next] = false;
 588         CHECK_MAPS_EQUAL();
 589       } else {
 590         // Check that it wasn't there already and then add it.
 591         ZoneSplayTree<TestConfig>::Locator loc;
 592         CHECK(!tree.Find(next, &loc));
 593         CHECK(tree.Insert(next, &loc));
 594         CHECK_EQ(next, loc.key());
 595         loc.set_value(3 * next);
 596         seen[next] = true;
 597         CHECK_MAPS_EQUAL();
 598       }
 599       int val = PseudoRandom(j, i) % kLimit;
 600       if (seen[val]) {
 601         ZoneSplayTree<TestConfig>::Locator loc;
 602         CHECK(tree.FindGreatestLessThan(val, &loc));
 603         CHECK_EQ(loc.key(), val);
 604         break;
 605       }
 606       val = PseudoRandom(i + j, i - j) % kLimit;
 607       if (seen[val]) {
 608         ZoneSplayTree<TestConfig>::Locator loc;
 609         CHECK(tree.FindLeastGreaterThan(val, &loc));
 610         CHECK_EQ(loc.key(), val);
 611         break;
 612       }
 613     }
 614   }
 615 }
 616
 617
 618 TEST(DispatchTableConstruction) {
 619   v8::internal::V8::Initialize(NULL);
 620   // Initialize test data.
 621   static const int kLimit = 1000;
 622   static const int kRangeCount = 8;
 623   static const int kRangeSize = 16;
 624   uc16 ranges[kRangeCount][2 * kRangeSize];
 625   for (int i = 0; i < kRangeCount; i++) {
 626     Vector<uc16> range(ranges[i], 2 * kRangeSize);
 627     for (int j = 0; j < 2 * kRangeSize; j++) {
 628       range[j] = PseudoRandom(i + 25, j + 87) % kLimit;
 629     }
 630     range.Sort();
 631     for (int j = 1; j < 2 * kRangeSize; j++) {
 632       CHECK(range[j-1] <= range[j]);
 633     }
 634   }
 635   // Enter test data into dispatch table.
 636   Zone zone(CcTest::i_isolate());
 637   DispatchTable table(&zone);
 638   for (int i = 0; i < kRangeCount; i++) {
 639     uc16* range = ranges[i];
 640     for (int j = 0; j < 2 * kRangeSize; j += 2)
 641       table.AddRange(CharacterRange(range[j], range[j + 1]), i, &zone);
 642   }
 643   // Check that the table looks as we would expect
 644   for (int p = 0; p < kLimit; p++) {
 645     OutSet* outs = table.Get(p);
 646     for (int j = 0; j < kRangeCount; j++) {
 647       uc16* range = ranges[j];
 648       bool is_on = false;
 649       for (int k = 0; !is_on && (k < 2 * kRangeSize); k += 2)
 650         is_on = (range[k] <= p && p <= range[k + 1]);
 651       CHECK_EQ(is_on, outs->Get(j));
 652     }
 653   }
 654 }
 655
 656
 657 // Test of debug-only syntax.
 658 #ifdef DEBUG
 659
 660 TEST(ParsePossessiveRepetition) {
 661   bool old_flag_value = FLAG_regexp_possessive_quantifier;
 662
 663   // Enable possessive quantifier syntax.
 664   FLAG_regexp_possessive_quantifier = true;
 665
 666   CHECK_PARSE_EQ("a*+", "(# 0 - p 'a')");
 667   CHECK_PARSE_EQ("a++", "(# 1 - p 'a')");
 668   CHECK_PARSE_EQ("a?+", "(# 0 1 p 'a')");
 669   CHECK_PARSE_EQ("a{10,20}+", "(# 10 20 p 'a')");
 670   CHECK_PARSE_EQ("za{10,20}+b", "(: 'z' (# 10 20 p 'a') 'b')");
 671
 672   // Disable possessive quantifier syntax.
 673   FLAG_regexp_possessive_quantifier = false;
 674
 675   CHECK_PARSE_ERROR("a*+");
 676   CHECK_PARSE_ERROR("a++");
 677   CHECK_PARSE_ERROR("a?+");
 678   CHECK_PARSE_ERROR("a{10,20}+");
 679   CHECK_PARSE_ERROR("a{10,20}+b");
 680
 681   FLAG_regexp_possessive_quantifier = old_flag_value;
 682 }
 683
 684 #endif
 685
 686 // Tests of interpreter.
 687
 688
 689 #ifndef V8_INTERPRETED_REGEXP
 690
 691 #if V8_TARGET_ARCH_IA32
 692 typedef RegExpMacroAssemblerIA32 ArchRegExpMacroAssembler;
 693 #elif V8_TARGET_ARCH_X64
 694 typedef RegExpMacroAssemblerX64 ArchRegExpMacroAssembler;
 695 #elif V8_TARGET_ARCH_ARM
 696 typedef RegExpMacroAssemblerARM ArchRegExpMacroAssembler;
 697 #elif V8_TARGET_ARCH_ARM64
 698 typedef RegExpMacroAssemblerARM64 ArchRegExpMacroAssembler;
 699 #elif V8_TARGET_ARCH_MIPS
 700 typedef RegExpMacroAssemblerMIPS ArchRegExpMacroAssembler;
 701 #endif
 702
 703 class ContextInitializer {
 704  public:
 705   ContextInitializer()
 706       : scope_(CcTest::isolate()),
 707         env_(v8::Context::New(CcTest::isolate())) {
 708     env_->Enter();
 709   }
 710   ~ContextInitializer() {
 711     env_->Exit();
 712   }
 713  private:
 714   v8::HandleScope scope_;
 715   v8::Handle<v8::Context> env_;
 716 };
 717
 718
 719 static ArchRegExpMacroAssembler::Result Execute(Code* code,
 720                                                 String* input,
 721                                                 int start_offset,
 722                                                 const byte* input_start,
 723                                                 const byte* input_end,
 724                                                 int* captures) {
 725   return NativeRegExpMacroAssembler::Execute(
 726       code,
 727       input,
 728       start_offset,
 729       input_start,
 730       input_end,
 731       captures,
 732       0,
 733       CcTest::i_isolate());
 734 }
 735
 736
 737 TEST(MacroAssemblerNativeSuccess) {
 738   v8::V8::Initialize();
 739   ContextInitializer initializer;
 740   Isolate* isolate = CcTest::i_isolate();
 741   Factory* factory = isolate->factory();
 742   Zone zone(isolate);
 743
 744   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 4, &zone);
 745
 746   m.Succeed();
 747
 748   Handle<String> source = factory->NewStringFromStaticAscii("");
 749   Handle<Object> code_object = m.GetCode(source);
 750   Handle<Code> code = Handle<Code>::cast(code_object);
 751
 752   int captures[4] = {42, 37, 87, 117};
 753   Handle<String> input = factory->NewStringFromStaticAscii("foofoo");
 754   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
 755   const byte* start_adr =
 756       reinterpret_cast<const byte*>(seq_input->GetCharsAddress());
 757
 758   NativeRegExpMacroAssembler::Result result =
 759       Execute(*code,
 760               *input,
 761               0,
 762               start_adr,
 763               start_adr + seq_input->length(),
 764               captures);
 765
 766   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
 767   CHECK_EQ(-1, captures[0]);
 768   CHECK_EQ(-1, captures[1]);
 769   CHECK_EQ(-1, captures[2]);
 770   CHECK_EQ(-1, captures[3]);
 771 }
 772
 773
 774 TEST(MacroAssemblerNativeSimple) {
 775   v8::V8::Initialize();
 776   ContextInitializer initializer;
 777   Isolate* isolate = CcTest::i_isolate();
 778   Factory* factory = isolate->factory();
 779   Zone zone(isolate);
 780
 781   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 4, &zone);
 782
 783   Label fail, backtrack;
 784   m.PushBacktrack(&fail);
 785   m.CheckNotAtStart(NULL);
 786   m.LoadCurrentCharacter(2, NULL);
 787   m.CheckNotCharacter('o', NULL);
 788   m.LoadCurrentCharacter(1, NULL, false);
 789   m.CheckNotCharacter('o', NULL);
 790   m.LoadCurrentCharacter(0, NULL, false);
 791   m.CheckNotCharacter('f', NULL);
 792   m.WriteCurrentPositionToRegister(0, 0);
 793   m.WriteCurrentPositionToRegister(1, 3);
 794   m.AdvanceCurrentPosition(3);
 795   m.PushBacktrack(&backtrack);
 796   m.Succeed();
 797   m.Bind(&backtrack);
 798   m.Backtrack();
 799   m.Bind(&fail);
 800   m.Fail();
 801
 802   Handle<String> source = factory->NewStringFromStaticAscii("^foo");
 803   Handle<Object> code_object = m.GetCode(source);
 804   Handle<Code> code = Handle<Code>::cast(code_object);
 805
 806   int captures[4] = {42, 37, 87, 117};
 807   Handle<String> input = factory->NewStringFromStaticAscii("foofoo");
 808   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
 809   Address start_adr = seq_input->GetCharsAddress();
 810
 811   NativeRegExpMacroAssembler::Result result =
 812       Execute(*code,
 813               *input,
 814               0,
 815               start_adr,
 816               start_adr + input->length(),
 817               captures);
 818
 819   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
 820   CHECK_EQ(0, captures[0]);
 821   CHECK_EQ(3, captures[1]);
 822   CHECK_EQ(-1, captures[2]);
 823   CHECK_EQ(-1, captures[3]);
 824
 825   input = factory->NewStringFromStaticAscii("barbarbar");
 826   seq_input = Handle<SeqOneByteString>::cast(input);
 827   start_adr = seq_input->GetCharsAddress();
 828
 829   result = Execute(*code,
 830                    *input,
 831                    0,
 832                    start_adr,
 833                    start_adr + input->length(),
 834                    captures);
 835
 836   CHECK_EQ(NativeRegExpMacroAssembler::FAILURE, result);
 837 }
 838
 839
 840 TEST(MacroAssemblerNativeSimpleUC16) {
 841   v8::V8::Initialize();
 842   ContextInitializer initializer;
 843   Isolate* isolate = CcTest::i_isolate();
 844   Factory* factory = isolate->factory();
 845   Zone zone(isolate);
 846
 847   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::UC16, 4, &zone);
 848
 849   Label fail, backtrack;
 850   m.PushBacktrack(&fail);
 851   m.CheckNotAtStart(NULL);
 852   m.LoadCurrentCharacter(2, NULL);
 853   m.CheckNotCharacter('o', NULL);
 854   m.LoadCurrentCharacter(1, NULL, false);
 855   m.CheckNotCharacter('o', NULL);
 856   m.LoadCurrentCharacter(0, NULL, false);
 857   m.CheckNotCharacter('f', NULL);
 858   m.WriteCurrentPositionToRegister(0, 0);
 859   m.WriteCurrentPositionToRegister(1, 3);
 860   m.AdvanceCurrentPosition(3);
 861   m.PushBacktrack(&backtrack);
 862   m.Succeed();
 863   m.Bind(&backtrack);
 864   m.Backtrack();
 865   m.Bind(&fail);
 866   m.Fail();
 867
 868   Handle<String> source = factory->NewStringFromStaticAscii("^foo");
 869   Handle<Object> code_object = m.GetCode(source);
 870   Handle<Code> code = Handle<Code>::cast(code_object);
 871
 872   int captures[4] = {42, 37, 87, 117};
 873   const uc16 input_data[6] = {'f', 'o', 'o', 'f', 'o',
 874                               static_cast<uc16>(0x2603)};
 875   Handle<String> input = factory->NewStringFromTwoByte(
 876       Vector<const uc16>(input_data, 6)).ToHandleChecked();
 877   Handle<SeqTwoByteString> seq_input = Handle<SeqTwoByteString>::cast(input);
 878   Address start_adr = seq_input->GetCharsAddress();
 879
 880   NativeRegExpMacroAssembler::Result result =
 881       Execute(*code,
 882               *input,
 883               0,
 884               start_adr,
 885               start_adr + input->length(),
 886               captures);
 887
 888   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
 889   CHECK_EQ(0, captures[0]);
 890   CHECK_EQ(3, captures[1]);
 891   CHECK_EQ(-1, captures[2]);
 892   CHECK_EQ(-1, captures[3]);
 893
 894   const uc16 input_data2[9] = {'b', 'a', 'r', 'b', 'a', 'r', 'b', 'a',
 895                                static_cast<uc16>(0x2603)};
 896   input = factory->NewStringFromTwoByte(
 897       Vector<const uc16>(input_data2, 9)).ToHandleChecked();
 898   seq_input = Handle<SeqTwoByteString>::cast(input);
 899   start_adr = seq_input->GetCharsAddress();
 900
 901   result = Execute(*code,
 902                    *input,
 903                    0,
 904                    start_adr,
 905                    start_adr + input->length() * 2,
 906                    captures);
 907
 908   CHECK_EQ(NativeRegExpMacroAssembler::FAILURE, result);
 909 }
 910
 911
 912 TEST(MacroAssemblerNativeBacktrack) {
 913   v8::V8::Initialize();
 914   ContextInitializer initializer;
 915   Isolate* isolate = CcTest::i_isolate();
 916   Factory* factory = isolate->factory();
 917   Zone zone(isolate);
 918
 919   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 0, &zone);
 920
 921   Label fail;
 922   Label backtrack;
 923   m.LoadCurrentCharacter(10, &fail);
 924   m.Succeed();
 925   m.Bind(&fail);
 926   m.PushBacktrack(&backtrack);
 927   m.LoadCurrentCharacter(10, NULL);
 928   m.Succeed();
 929   m.Bind(&backtrack);
 930   m.Fail();
 931
 932   Handle<String> source = factory->NewStringFromStaticAscii("..........");
 933   Handle<Object> code_object = m.GetCode(source);
 934   Handle<Code> code = Handle<Code>::cast(code_object);
 935
 936   Handle<String> input = factory->NewStringFromStaticAscii("foofoo");
 937   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
 938   Address start_adr = seq_input->GetCharsAddress();
 939
 940   NativeRegExpMacroAssembler::Result result =
 941       Execute(*code,
 942               *input,
 943               0,
 944               start_adr,
 945               start_adr + input->length(),
 946               NULL);
 947
 948   CHECK_EQ(NativeRegExpMacroAssembler::FAILURE, result);
 949 }
 950
 951
 952 TEST(MacroAssemblerNativeBackReferenceASCII) {
 953   v8::V8::Initialize();
 954   ContextInitializer initializer;
 955   Isolate* isolate = CcTest::i_isolate();
 956   Factory* factory = isolate->factory();
 957   Zone zone(isolate);
 958
 959   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 4, &zone);
 960
 961   m.WriteCurrentPositionToRegister(0, 0);
 962   m.AdvanceCurrentPosition(2);
 963   m.WriteCurrentPositionToRegister(1, 0);
 964   Label nomatch;
 965   m.CheckNotBackReference(0, &nomatch);
 966   m.Fail();
 967   m.Bind(&nomatch);
 968   m.AdvanceCurrentPosition(2);
 969   Label missing_match;
 970   m.CheckNotBackReference(0, &missing_match);
 971   m.WriteCurrentPositionToRegister(2, 0);
 972   m.Succeed();
 973   m.Bind(&missing_match);
 974   m.Fail();
 975
 976   Handle<String> source = factory->NewStringFromStaticAscii("^(..)..\1");
 977   Handle<Object> code_object = m.GetCode(source);
 978   Handle<Code> code = Handle<Code>::cast(code_object);
 979
 980   Handle<String> input = factory->NewStringFromStaticAscii("fooofo");
 981   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
 982   Address start_adr = seq_input->GetCharsAddress();
 983
 984   int output[4];
 985   NativeRegExpMacroAssembler::Result result =
 986       Execute(*code,
 987               *input,
 988               0,
 989               start_adr,
 990               start_adr + input->length(),
 991               output);
 992
 993   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
 994   CHECK_EQ(0, output[0]);
 995   CHECK_EQ(2, output[1]);
 996   CHECK_EQ(6, output[2]);
 997   CHECK_EQ(-1, output[3]);
 998 }
 999
1000
1001 TEST(MacroAssemblerNativeBackReferenceUC16) {
1002   v8::V8::Initialize();
1003   ContextInitializer initializer;
1004   Isolate* isolate = CcTest::i_isolate();
1005   Factory* factory = isolate->factory();
1006   Zone zone(isolate);
1007
1008   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::UC16, 4, &zone);
1009
1010   m.WriteCurrentPositionToRegister(0, 0);
1011   m.AdvanceCurrentPosition(2);
1012   m.WriteCurrentPositionToRegister(1, 0);
1013   Label nomatch;
1014   m.CheckNotBackReference(0, &nomatch);
1015   m.Fail();
1016   m.Bind(&nomatch);
1017   m.AdvanceCurrentPosition(2);
1018   Label missing_match;
1019   m.CheckNotBackReference(0, &missing_match);
1020   m.WriteCurrentPositionToRegister(2, 0);
1021   m.Succeed();
1022   m.Bind(&missing_match);
1023   m.Fail();
1024
1025   Handle<String> source = factory->NewStringFromStaticAscii("^(..)..\1");
1026   Handle<Object> code_object = m.GetCode(source);
1027   Handle<Code> code = Handle<Code>::cast(code_object);
1028
1029   const uc16 input_data[6] = {'f', 0x2028, 'o', 'o', 'f', 0x2028};
1030   Handle<String> input = factory->NewStringFromTwoByte(
1031       Vector<const uc16>(input_data, 6)).ToHandleChecked();
1032   Handle<SeqTwoByteString> seq_input = Handle<SeqTwoByteString>::cast(input);
1033   Address start_adr = seq_input->GetCharsAddress();
1034
1035   int output[4];
1036   NativeRegExpMacroAssembler::Result result =
1037       Execute(*code,
1038               *input,
1039               0,
1040               start_adr,
1041               start_adr + input->length() * 2,
1042               output);
1043
1044   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1045   CHECK_EQ(0, output[0]);
1046   CHECK_EQ(2, output[1]);
1047   CHECK_EQ(6, output[2]);
1048   CHECK_EQ(-1, output[3]);
1049 }
1050
1051
1052
1053 TEST(MacroAssemblernativeAtStart) {
1054   v8::V8::Initialize();
1055   ContextInitializer initializer;
1056   Isolate* isolate = CcTest::i_isolate();
1057   Factory* factory = isolate->factory();
1058   Zone zone(isolate);
1059
1060   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 0, &zone);
1061
1062   Label not_at_start, newline, fail;
1063   m.CheckNotAtStart(&not_at_start);
1064   // Check that prevchar = '\n' and current = 'f'.
1065   m.CheckCharacter('\n', &newline);
1066   m.Bind(&fail);
1067   m.Fail();
1068   m.Bind(&newline);
1069   m.LoadCurrentCharacter(0, &fail);
1070   m.CheckNotCharacter('f', &fail);
1071   m.Succeed();
1072
1073   m.Bind(&not_at_start);
1074   // Check that prevchar = 'o' and current = 'b'.
1075   Label prevo;
1076   m.CheckCharacter('o', &prevo);
1077   m.Fail();
1078   m.Bind(&prevo);
1079   m.LoadCurrentCharacter(0, &fail);
1080   m.CheckNotCharacter('b', &fail);
1081   m.Succeed();
1082
1083   Handle<String> source = factory->NewStringFromStaticAscii("(^f|ob)");
1084   Handle<Object> code_object = m.GetCode(source);
1085   Handle<Code> code = Handle<Code>::cast(code_object);
1086
1087   Handle<String> input = factory->NewStringFromStaticAscii("foobar");
1088   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1089   Address start_adr = seq_input->GetCharsAddress();
1090
1091   NativeRegExpMacroAssembler::Result result =
1092       Execute(*code,
1093               *input,
1094               0,
1095               start_adr,
1096               start_adr + input->length(),
1097               NULL);
1098
1099   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1100
1101   result = Execute(*code,
1102                    *input,
1103                    3,
1104                    start_adr + 3,
1105                    start_adr + input->length(),
1106                    NULL);
1107
1108   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1109 }
1110
1111
1112 TEST(MacroAssemblerNativeBackRefNoCase) {
1113   v8::V8::Initialize();
1114   ContextInitializer initializer;
1115   Isolate* isolate = CcTest::i_isolate();
1116   Factory* factory = isolate->factory();
1117   Zone zone(isolate);
1118
1119   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 4, &zone);
1120
1121   Label fail, succ;
1122
1123   m.WriteCurrentPositionToRegister(0, 0);
1124   m.WriteCurrentPositionToRegister(2, 0);
1125   m.AdvanceCurrentPosition(3);
1126   m.WriteCurrentPositionToRegister(3, 0);
1127   m.CheckNotBackReferenceIgnoreCase(2, &fail);  // Match "AbC".
1128   m.CheckNotBackReferenceIgnoreCase(2, &fail);  // Match "ABC".
1129   Label expected_fail;
1130   m.CheckNotBackReferenceIgnoreCase(2, &expected_fail);
1131   m.Bind(&fail);
1132   m.Fail();
1133
1134   m.Bind(&expected_fail);
1135   m.AdvanceCurrentPosition(3);  // Skip "xYz"
1136   m.CheckNotBackReferenceIgnoreCase(2, &succ);
1137   m.Fail();
1138
1139   m.Bind(&succ);
1140   m.WriteCurrentPositionToRegister(1, 0);
1141   m.Succeed();
1142
1143   Handle<String> source =
1144       factory->NewStringFromStaticAscii("^(abc)\1\1(?!\1)...(?!\1)");
1145   Handle<Object> code_object = m.GetCode(source);
1146   Handle<Code> code = Handle<Code>::cast(code_object);
1147
1148   Handle<String> input =
1149       factory->NewStringFromStaticAscii("aBcAbCABCxYzab");
1150   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1151   Address start_adr = seq_input->GetCharsAddress();
1152
1153   int output[4];
1154   NativeRegExpMacroAssembler::Result result =
1155       Execute(*code,
1156               *input,
1157               0,
1158               start_adr,
1159               start_adr + input->length(),
1160               output);
1161
1162   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1163   CHECK_EQ(0, output[0]);
1164   CHECK_EQ(12, output[1]);
1165   CHECK_EQ(0, output[2]);
1166   CHECK_EQ(3, output[3]);
1167 }
1168
1169
1170
1171 TEST(MacroAssemblerNativeRegisters) {
1172   v8::V8::Initialize();
1173   ContextInitializer initializer;
1174   Isolate* isolate = CcTest::i_isolate();
1175   Factory* factory = isolate->factory();
1176   Zone zone(isolate);
1177
1178   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 6, &zone);
1179
1180   uc16 foo_chars[3] = {'f', 'o', 'o'};
1181   Vector<const uc16> foo(foo_chars, 3);
1182
1183   enum registers { out1, out2, out3, out4, out5, out6, sp, loop_cnt };
1184   Label fail;
1185   Label backtrack;
1186   m.WriteCurrentPositionToRegister(out1, 0);  // Output: [0]
1187   m.PushRegister(out1, RegExpMacroAssembler::kNoStackLimitCheck);
1188   m.PushBacktrack(&backtrack);
1189   m.WriteStackPointerToRegister(sp);
1190   // Fill stack and registers
1191   m.AdvanceCurrentPosition(2);
1192   m.WriteCurrentPositionToRegister(out1, 0);
1193   m.PushRegister(out1, RegExpMacroAssembler::kNoStackLimitCheck);
1194   m.PushBacktrack(&fail);
1195   // Drop backtrack stack frames.
1196   m.ReadStackPointerFromRegister(sp);
1197   // And take the first backtrack (to &backtrack)
1198   m.Backtrack();
1199
1200   m.PushCurrentPosition();
1201   m.AdvanceCurrentPosition(2);
1202   m.PopCurrentPosition();
1203
1204   m.Bind(&backtrack);
1205   m.PopRegister(out1);
1206   m.ReadCurrentPositionFromRegister(out1);
1207   m.AdvanceCurrentPosition(3);
1208   m.WriteCurrentPositionToRegister(out2, 0);  // [0,3]
1209
1210   Label loop;
1211   m.SetRegister(loop_cnt, 0);  // loop counter
1212   m.Bind(&loop);
1213   m.AdvanceRegister(loop_cnt, 1);
1214   m.AdvanceCurrentPosition(1);
1215   m.IfRegisterLT(loop_cnt, 3, &loop);
1216   m.WriteCurrentPositionToRegister(out3, 0);  // [0,3,6]
1217
1218   Label loop2;
1219   m.SetRegister(loop_cnt, 2);  // loop counter
1220   m.Bind(&loop2);
1221   m.AdvanceRegister(loop_cnt, -1);
1222   m.AdvanceCurrentPosition(1);
1223   m.IfRegisterGE(loop_cnt, 0, &loop2);
1224   m.WriteCurrentPositionToRegister(out4, 0);  // [0,3,6,9]
1225
1226   Label loop3;
1227   Label exit_loop3;
1228   m.PushRegister(out4, RegExpMacroAssembler::kNoStackLimitCheck);
1229   m.PushRegister(out4, RegExpMacroAssembler::kNoStackLimitCheck);
1230   m.ReadCurrentPositionFromRegister(out3);
1231   m.Bind(&loop3);
1232   m.AdvanceCurrentPosition(1);
1233   m.CheckGreedyLoop(&exit_loop3);
1234   m.GoTo(&loop3);
1235   m.Bind(&exit_loop3);
1236   m.PopCurrentPosition();
1237   m.WriteCurrentPositionToRegister(out5, 0);  // [0,3,6,9,9,-1]
1238
1239   m.Succeed();
1240
1241   m.Bind(&fail);
1242   m.Fail();
1243
1244   Handle<String> source =
1245       factory->NewStringFromStaticAscii("<loop test>");
1246   Handle<Object> code_object = m.GetCode(source);
1247   Handle<Code> code = Handle<Code>::cast(code_object);
1248
1249   // String long enough for test (content doesn't matter).
1250   Handle<String> input =
1251       factory->NewStringFromStaticAscii("foofoofoofoofoo");
1252   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1253   Address start_adr = seq_input->GetCharsAddress();
1254
1255   int output[6];
1256   NativeRegExpMacroAssembler::Result result =
1257       Execute(*code,
1258               *input,
1259               0,
1260               start_adr,
1261               start_adr + input->length(),
1262               output);
1263
1264   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1265   CHECK_EQ(0, output[0]);
1266   CHECK_EQ(3, output[1]);
1267   CHECK_EQ(6, output[2]);
1268   CHECK_EQ(9, output[3]);
1269   CHECK_EQ(9, output[4]);
1270   CHECK_EQ(-1, output[5]);
1271 }
1272
1273
1274 TEST(MacroAssemblerStackOverflow) {
1275   v8::V8::Initialize();
1276   ContextInitializer initializer;
1277   Isolate* isolate = CcTest::i_isolate();
1278   Factory* factory = isolate->factory();
1279   Zone zone(isolate);
1280
1281   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 0, &zone);
1282
1283   Label loop;
1284   m.Bind(&loop);
1285   m.PushBacktrack(&loop);
1286   m.GoTo(&loop);
1287
1288   Handle<String> source =
1289       factory->NewStringFromStaticAscii("<stack overflow test>");
1290   Handle<Object> code_object = m.GetCode(source);
1291   Handle<Code> code = Handle<Code>::cast(code_object);
1292
1293   // String long enough for test (content doesn't matter).
1294   Handle<String> input =
1295       factory->NewStringFromStaticAscii("dummy");
1296   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1297   Address start_adr = seq_input->GetCharsAddress();
1298
1299   NativeRegExpMacroAssembler::Result result =
1300       Execute(*code,
1301               *input,
1302               0,
1303               start_adr,
1304               start_adr + input->length(),
1305               NULL);
1306
1307   CHECK_EQ(NativeRegExpMacroAssembler::EXCEPTION, result);
1308   CHECK(isolate->has_pending_exception());
1309   isolate->clear_pending_exception();
1310 }
1311
1312
1313 TEST(MacroAssemblerNativeLotsOfRegisters) {
1314   v8::V8::Initialize();
1315   ContextInitializer initializer;
1316   Isolate* isolate = CcTest::i_isolate();
1317   Factory* factory = isolate->factory();
1318   Zone zone(isolate);
1319
1320   ArchRegExpMacroAssembler m(NativeRegExpMacroAssembler::ASCII, 2, &zone);
1321
1322   // At least 2048, to ensure the allocated space for registers
1323   // span one full page.
1324   const int large_number = 8000;
1325   m.WriteCurrentPositionToRegister(large_number, 42);
1326   m.WriteCurrentPositionToRegister(0, 0);
1327   m.WriteCurrentPositionToRegister(1, 1);
1328   Label done;
1329   m.CheckNotBackReference(0, &done);  // Performs a system-stack push.
1330   m.Bind(&done);
1331   m.PushRegister(large_number, RegExpMacroAssembler::kNoStackLimitCheck);
1332   m.PopRegister(1);
1333   m.Succeed();
1334
1335   Handle<String> source =
1336       factory->NewStringFromStaticAscii("<huge register space test>");
1337   Handle<Object> code_object = m.GetCode(source);
1338   Handle<Code> code = Handle<Code>::cast(code_object);
1339
1340   // String long enough for test (content doesn't matter).
1341   Handle<String> input =
1342       factory->NewStringFromStaticAscii("sample text");
1343   Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1344   Address start_adr = seq_input->GetCharsAddress();
1345
1346   int captures[2];
1347   NativeRegExpMacroAssembler::Result result =
1348       Execute(*code,
1349               *input,
1350               0,
1351               start_adr,
1352               start_adr + input->length(),
1353               captures);
1354
1355   CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1356   CHECK_EQ(0, captures[0]);
1357   CHECK_EQ(42, captures[1]);
1358
1359   isolate->clear_pending_exception();
1360 }
1361
1362 #else  // V8_INTERPRETED_REGEXP
1363
1364 TEST(MacroAssembler) {
1365   V8::Initialize(NULL);
1366   byte codes[1024];
1367   Zone zone(CcTest::i_isolate());
1368   RegExpMacroAssemblerIrregexp m(Vector<byte>(codes, 1024), &zone);
1369   // ^f(o)o.
1370   Label start, fail, backtrack;
1371
1372   m.SetRegister(4, 42);
1373   m.PushRegister(4, RegExpMacroAssembler::kNoStackLimitCheck);
1374   m.AdvanceRegister(4, 42);
1375   m.GoTo(&start);
1376   m.Fail();
1377   m.Bind(&start);
1378   m.PushBacktrack(&fail);
1379   m.CheckNotAtStart(NULL);
1380   m.LoadCurrentCharacter(0, NULL);
1381   m.CheckNotCharacter('f', NULL);
1382   m.LoadCurrentCharacter(1, NULL);
1383   m.CheckNotCharacter('o', NULL);
1384   m.LoadCurrentCharacter(2, NULL);
1385   m.CheckNotCharacter('o', NULL);
1386   m.WriteCurrentPositionToRegister(0, 0);
1387   m.WriteCurrentPositionToRegister(1, 3);
1388   m.WriteCurrentPositionToRegister(2, 1);
1389   m.WriteCurrentPositionToRegister(3, 2);
1390   m.AdvanceCurrentPosition(3);
1391   m.PushBacktrack(&backtrack);
1392   m.Succeed();
1393   m.Bind(&backtrack);
1394   m.ClearRegisters(2, 3);
1395   m.Backtrack();
1396   m.Bind(&fail);
1397   m.PopRegister(0);
1398   m.Fail();
1399
1400   Isolate* isolate = CcTest::i_isolate();
1401   Factory* factory = isolate->factory();
1402   HandleScope scope(isolate);
1403
1404   Handle<String> source = factory->NewStringFromStaticAscii("^f(o)o");
1405   Handle<ByteArray> array = Handle<ByteArray>::cast(m.GetCode(source));
1406   int captures[5];
1407
1408   const uc16 str1[] = {'f', 'o', 'o', 'b', 'a', 'r'};
1409   Handle<String> f1_16 = factory->NewStringFromTwoByte(
1410       Vector<const uc16>(str1, 6)).ToHandleChecked();
1411
1412   CHECK(IrregexpInterpreter::Match(isolate, array, f1_16, captures, 0));
1413   CHECK_EQ(0, captures[0]);
1414   CHECK_EQ(3, captures[1]);
1415   CHECK_EQ(1, captures[2]);
1416   CHECK_EQ(2, captures[3]);
1417   CHECK_EQ(84, captures[4]);
1418
1419   const uc16 str2[] = {'b', 'a', 'r', 'f', 'o', 'o'};
1420   Handle<String> f2_16 = factory->NewStringFromTwoByte(
1421       Vector<const uc16>(str2, 6)).ToHandleChecked();
1422
1423   CHECK(!IrregexpInterpreter::Match(isolate, array, f2_16, captures, 0));
1424   CHECK_EQ(42, captures[0]);
1425 }
1426
1427 #endif  // V8_INTERPRETED_REGEXP
1428
1429
1430 TEST(AddInverseToTable) {
1431   v8::internal::V8::Initialize(NULL);
1432   static const int kLimit = 1000;
1433   static const int kRangeCount = 16;
1434   for (int t = 0; t < 10; t++) {
1435     Zone zone(CcTest::i_isolate());
1436     ZoneList<CharacterRange>* ranges =
1437         new(&zone) ZoneList<CharacterRange>(kRangeCount, &zone);
1438     for (int i = 0; i < kRangeCount; i++) {
1439       int from = PseudoRandom(t + 87, i + 25) % kLimit;
1440       int to = from + (PseudoRandom(i + 87, t + 25) % (kLimit / 20));
1441       if (to > kLimit) to = kLimit;
1442       ranges->Add(CharacterRange(from, to), &zone);
1443     }
1444     DispatchTable table(&zone);
1445     DispatchTableConstructor cons(&table, false, &zone);
1446     cons.set_choice_index(0);
1447     cons.AddInverse(ranges);
1448     for (int i = 0; i < kLimit; i++) {
1449       bool is_on = false;
1450       for (int j = 0; !is_on && j < kRangeCount; j++)
1451         is_on = ranges->at(j).Contains(i);
1452       OutSet* set = table.Get(i);
1453       CHECK_EQ(is_on, set->Get(0) == false);
1454     }
1455   }
1456   Zone zone(CcTest::i_isolate());
1457   ZoneList<CharacterRange>* ranges =
1458       new(&zone) ZoneList<CharacterRange>(1, &zone);
1459   ranges->Add(CharacterRange(0xFFF0, 0xFFFE), &zone);
1460   DispatchTable table(&zone);
1461   DispatchTableConstructor cons(&table, false, &zone);
1462   cons.set_choice_index(0);
1463   cons.AddInverse(ranges);
1464   CHECK(!table.Get(0xFFFE)->Get(0));
1465   CHECK(table.Get(0xFFFF)->Get(0));
1466 }
1467
1468
1469 static uc32 canonicalize(uc32 c) {
1470   unibrow::uchar canon[unibrow::Ecma262Canonicalize::kMaxWidth];
1471   int count = unibrow::Ecma262Canonicalize::Convert(c, '\0', canon, NULL);
1472   if (count == 0) {
1473     return c;
1474   } else {
1475     CHECK_EQ(1, count);
1476     return canon[0];
1477   }
1478 }
1479
1480
1481 TEST(LatinCanonicalize) {
1482   unibrow::Mapping<unibrow::Ecma262UnCanonicalize> un_canonicalize;
1483   for (char lower = 'a'; lower <= 'z'; lower++) {
1484     char upper = lower + ('A' - 'a');
1485     CHECK_EQ(canonicalize(lower), canonicalize(upper));
1486     unibrow::uchar uncanon[unibrow::Ecma262UnCanonicalize::kMaxWidth];
1487     int length = un_canonicalize.get(lower, '\0', uncanon);
1488     CHECK_EQ(2, length);
1489     CHECK_EQ(upper, uncanon[0]);
1490     CHECK_EQ(lower, uncanon[1]);
1491   }
1492   for (uc32 c = 128; c < (1 << 21); c++)
1493     CHECK_GE(canonicalize(c), 128);
1494   unibrow::Mapping<unibrow::ToUppercase> to_upper;
1495   // Canonicalization is only defined for the Basic Multilingual Plane.
1496   for (uc32 c = 0; c < (1 << 16); c++) {
1497     unibrow::uchar upper[unibrow::ToUppercase::kMaxWidth];
1498     int length = to_upper.get(c, '\0', upper);
1499     if (length == 0) {
1500       length = 1;
1501       upper[0] = c;
1502     }
1503     uc32 u = upper[0];
1504     if (length > 1 || (c >= 128 && u < 128))
1505       u = c;
1506     CHECK_EQ(u, canonicalize(c));
1507   }
1508 }
1509
1510
1511 static uc32 CanonRangeEnd(uc32 c) {
1512   unibrow::uchar canon[unibrow::CanonicalizationRange::kMaxWidth];
1513   int count = unibrow::CanonicalizationRange::Convert(c, '\0', canon, NULL);
1514   if (count == 0) {
1515     return c;
1516   } else {
1517     CHECK_EQ(1, count);
1518     return canon[0];
1519   }
1520 }
1521
1522
1523 TEST(RangeCanonicalization) {
1524   // Check that we arrive at the same result when using the basic
1525   // range canonicalization primitives as when using immediate
1526   // canonicalization.
1527   unibrow::Mapping<unibrow::Ecma262UnCanonicalize> un_canonicalize;
1528   int block_start = 0;
1529   while (block_start <= 0xFFFF) {
1530     uc32 block_end = CanonRangeEnd(block_start);
1531     unsigned block_length = block_end - block_start + 1;
1532     if (block_length > 1) {
1533       unibrow::uchar first[unibrow::Ecma262UnCanonicalize::kMaxWidth];
1534       int first_length = un_canonicalize.get(block_start, '\0', first);
1535       for (unsigned i = 1; i < block_length; i++) {
1536         unibrow::uchar succ[unibrow::Ecma262UnCanonicalize::kMaxWidth];
1537         int succ_length = un_canonicalize.get(block_start + i, '\0', succ);
1538         CHECK_EQ(first_length, succ_length);
1539         for (int j = 0; j < succ_length; j++) {
1540           int calc = first[j] + i;
1541           int found = succ[j];
1542           CHECK_EQ(calc, found);
1543         }
1544       }
1545     }
1546     block_start = block_start + block_length;
1547   }
1548 }
1549
1550
1551 TEST(UncanonicalizeEquivalence) {
1552   unibrow::Mapping<unibrow::Ecma262UnCanonicalize> un_canonicalize;
1553   unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
1554   for (int i = 0; i < (1 << 16); i++) {
1555     int length = un_canonicalize.get(i, '\0', chars);
1556     for (int j = 0; j < length; j++) {
1557       unibrow::uchar chars2[unibrow::Ecma262UnCanonicalize::kMaxWidth];
1558       int length2 = un_canonicalize.get(chars[j], '\0', chars2);
1559       CHECK_EQ(length, length2);
1560       for (int k = 0; k < length; k++)
1561         CHECK_EQ(static_cast<int>(chars[k]), static_cast<int>(chars2[k]));
1562     }
1563   }
1564 }
1565
1566
1567 static void TestRangeCaseIndependence(CharacterRange input,
1568                                       Vector<CharacterRange> expected) {
1569   Zone zone(CcTest::i_isolate());
1570   int count = expected.length();
1571   ZoneList<CharacterRange>* list =
1572       new(&zone) ZoneList<CharacterRange>(count, &zone);
1573   input.AddCaseEquivalents(list, false, &zone);
1574   CHECK_EQ(count, list->length());
1575   for (int i = 0; i < list->length(); i++) {
1576     CHECK_EQ(expected[i].from(), list->at(i).from());
1577     CHECK_EQ(expected[i].to(), list->at(i).to());
1578   }
1579 }
1580
1581
1582 static void TestSimpleRangeCaseIndependence(CharacterRange input,
1583                                             CharacterRange expected) {
1584   EmbeddedVector<CharacterRange, 1> vector;
1585   vector[0] = expected;
1586   TestRangeCaseIndependence(input, vector);
1587 }
1588
1589
1590 TEST(CharacterRangeCaseIndependence) {
1591   v8::internal::V8::Initialize(NULL);
1592   TestSimpleRangeCaseIndependence(CharacterRange::Singleton('a'),
1593                                   CharacterRange::Singleton('A'));
1594   TestSimpleRangeCaseIndependence(CharacterRange::Singleton('z'),
1595                                   CharacterRange::Singleton('Z'));
1596   TestSimpleRangeCaseIndependence(CharacterRange('a', 'z'),
1597                                   CharacterRange('A', 'Z'));
1598   TestSimpleRangeCaseIndependence(CharacterRange('c', 'f'),
1599                                   CharacterRange('C', 'F'));
1600   TestSimpleRangeCaseIndependence(CharacterRange('a', 'b'),
1601                                   CharacterRange('A', 'B'));
1602   TestSimpleRangeCaseIndependence(CharacterRange('y', 'z'),
1603                                   CharacterRange('Y', 'Z'));
1604   TestSimpleRangeCaseIndependence(CharacterRange('a' - 1, 'z' + 1),
1605                                   CharacterRange('A', 'Z'));
1606   TestSimpleRangeCaseIndependence(CharacterRange('A', 'Z'),
1607                                   CharacterRange('a', 'z'));
1608   TestSimpleRangeCaseIndependence(CharacterRange('C', 'F'),
1609                                   CharacterRange('c', 'f'));
1610   TestSimpleRangeCaseIndependence(CharacterRange('A' - 1, 'Z' + 1),
1611                                   CharacterRange('a', 'z'));
1612   // Here we need to add [l-z] to complete the case independence of
1613   // [A-Za-z] but we expect [a-z] to be added since we always add a
1614   // whole block at a time.
1615   TestSimpleRangeCaseIndependence(CharacterRange('A', 'k'),
1616                                   CharacterRange('a', 'z'));
1617 }
1618
1619
1620 static bool InClass(uc16 c, ZoneList<CharacterRange>* ranges) {
1621   if (ranges == NULL)
1622     return false;
1623   for (int i = 0; i < ranges->length(); i++) {
1624     CharacterRange range = ranges->at(i);
1625     if (range.from() <= c && c <= range.to())
1626       return true;
1627   }
1628   return false;
1629 }
1630
1631
1632 TEST(CharClassDifference) {
1633   v8::internal::V8::Initialize(NULL);
1634   Zone zone(CcTest::i_isolate());
1635   ZoneList<CharacterRange>* base =
1636       new(&zone) ZoneList<CharacterRange>(1, &zone);
1637   base->Add(CharacterRange::Everything(), &zone);
1638   Vector<const int> overlay = CharacterRange::GetWordBounds();
1639   ZoneList<CharacterRange>* included = NULL;
1640   ZoneList<CharacterRange>* excluded = NULL;
1641   CharacterRange::Split(base, overlay, &included, &excluded, &zone);
1642   for (int i = 0; i < (1 << 16); i++) {
1643     bool in_base = InClass(i, base);
1644     if (in_base) {
1645       bool in_overlay = false;
1646       for (int j = 0; !in_overlay && j < overlay.length(); j += 2) {
1647         if (overlay[j] <= i && i < overlay[j+1])
1648           in_overlay = true;
1649       }
1650       CHECK_EQ(in_overlay, InClass(i, included));
1651       CHECK_EQ(!in_overlay, InClass(i, excluded));
1652     } else {
1653       CHECK(!InClass(i, included));
1654       CHECK(!InClass(i, excluded));
1655     }
1656   }
1657 }
1658
1659
1660 TEST(CanonicalizeCharacterSets) {
1661   v8::internal::V8::Initialize(NULL);
1662   Zone zone(CcTest::i_isolate());
1663   ZoneList<CharacterRange>* list =
1664       new(&zone) ZoneList<CharacterRange>(4, &zone);
1665   CharacterSet set(list);
1666
1667   list->Add(CharacterRange(10, 20), &zone);
1668   list->Add(CharacterRange(30, 40), &zone);
1669   list->Add(CharacterRange(50, 60), &zone);
1670   set.Canonicalize();
1671   ASSERT_EQ(3, list->length());
1672   ASSERT_EQ(10, list->at(0).from());
1673   ASSERT_EQ(20, list->at(0).to());
1674   ASSERT_EQ(30, list->at(1).from());
1675   ASSERT_EQ(40, list->at(1).to());
1676   ASSERT_EQ(50, list->at(2).from());
1677   ASSERT_EQ(60, list->at(2).to());
1678
1679   list->Rewind(0);
1680   list->Add(CharacterRange(10, 20), &zone);
1681   list->Add(CharacterRange(50, 60), &zone);
1682   list->Add(CharacterRange(30, 40), &zone);
1683   set.Canonicalize();
1684   ASSERT_EQ(3, list->length());
1685   ASSERT_EQ(10, list->at(0).from());
1686   ASSERT_EQ(20, list->at(0).to());
1687   ASSERT_EQ(30, list->at(1).from());
1688   ASSERT_EQ(40, list->at(1).to());
1689   ASSERT_EQ(50, list->at(2).from());
1690   ASSERT_EQ(60, list->at(2).to());
1691
1692   list->Rewind(0);
1693   list->Add(CharacterRange(30, 40), &zone);
1694   list->Add(CharacterRange(10, 20), &zone);
1695   list->Add(CharacterRange(25, 25), &zone);
1696   list->Add(CharacterRange(100, 100), &zone);
1697   list->Add(CharacterRange(1, 1), &zone);
1698   set.Canonicalize();
1699   ASSERT_EQ(5, list->length());
1700   ASSERT_EQ(1, list->at(0).from());
1701   ASSERT_EQ(1, list->at(0).to());
1702   ASSERT_EQ(10, list->at(1).from());
1703   ASSERT_EQ(20, list->at(1).to());
1704   ASSERT_EQ(25, list->at(2).from());
1705   ASSERT_EQ(25, list->at(2).to());
1706   ASSERT_EQ(30, list->at(3).from());
1707   ASSERT_EQ(40, list->at(3).to());
1708   ASSERT_EQ(100, list->at(4).from());
1709   ASSERT_EQ(100, list->at(4).to());
1710
1711   list->Rewind(0);
1712   list->Add(CharacterRange(10, 19), &zone);
1713   list->Add(CharacterRange(21, 30), &zone);
1714   list->Add(CharacterRange(20, 20), &zone);
1715   set.Canonicalize();
1716   ASSERT_EQ(1, list->length());
1717   ASSERT_EQ(10, list->at(0).from());
1718   ASSERT_EQ(30, list->at(0).to());
1719 }
1720
1721
1722 TEST(CharacterRangeMerge) {
1723   v8::internal::V8::Initialize(NULL);
1724   Zone zone(CcTest::i_isolate());
1725   ZoneList<CharacterRange> l1(4, &zone);
1726   ZoneList<CharacterRange> l2(4, &zone);
1727   // Create all combinations of intersections of ranges, both singletons and
1728   // longer.
1729
1730   int offset = 0;
1731
1732   // The five kinds of singleton intersections:
1733   //     X
1734   //   Y      - outside before
1735   //    Y     - outside touching start
1736   //     Y    - overlap
1737   //      Y   - outside touching end
1738   //       Y  - outside after
1739
1740   for (int i = 0; i < 5; i++) {
1741     l1.Add(CharacterRange::Singleton(offset + 2), &zone);
1742     l2.Add(CharacterRange::Singleton(offset + i), &zone);
1743     offset += 6;
1744   }
1745
1746   // The seven kinds of singleton/non-singleton intersections:
1747   //    XXX
1748   //  Y        - outside before
1749   //   Y       - outside touching start
1750   //    Y      - inside touching start
1751   //     Y     - entirely inside
1752   //      Y    - inside touching end
1753   //       Y   - outside touching end
1754   //        Y  - disjoint after
1755
1756   for (int i = 0; i < 7; i++) {
1757     l1.Add(CharacterRange::Range(offset + 2, offset + 4), &zone);
1758     l2.Add(CharacterRange::Singleton(offset + i), &zone);
1759     offset += 8;
1760   }
1761
1762   // The eleven kinds of non-singleton intersections:
1763   //
1764   //       XXXXXXXX
1765   // YYYY                  - outside before.
1766   //   YYYY                - outside touching start.
1767   //     YYYY              - overlapping start
1768   //       YYYY            - inside touching start
1769   //         YYYY          - entirely inside
1770   //           YYYY        - inside touching end
1771   //             YYYY      - overlapping end
1772   //               YYYY    - outside touching end
1773   //                 YYYY  - outside after
1774   //       YYYYYYYY        - identical
1775   //     YYYYYYYYYYYY      - containing entirely.
1776
1777   for (int i = 0; i < 9; i++) {
1778     l1.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);  // Length 8.
1779     l2.Add(CharacterRange::Range(offset + 2 * i, offset + 2 * i + 3), &zone);
1780     offset += 22;
1781   }
1782   l1.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);
1783   l2.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);
1784   offset += 22;
1785   l1.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);
1786   l2.Add(CharacterRange::Range(offset + 4, offset + 17), &zone);
1787   offset += 22;
1788
1789   // Different kinds of multi-range overlap:
1790   // XXXXXXXXXXXXXXXXXXXXXX         XXXXXXXXXXXXXXXXXXXXXX
1791   //   YYYY  Y  YYYY  Y  YYYY  Y  YYYY  Y  YYYY  Y  YYYY  Y
1792
1793   l1.Add(CharacterRange::Range(offset, offset + 21), &zone);
1794   l1.Add(CharacterRange::Range(offset + 31, offset + 52), &zone);
1795   for (int i = 0; i < 6; i++) {
1796     l2.Add(CharacterRange::Range(offset + 2, offset + 5), &zone);
1797     l2.Add(CharacterRange::Singleton(offset + 8), &zone);
1798     offset += 9;
1799   }
1800
1801   ASSERT(CharacterRange::IsCanonical(&l1));
1802   ASSERT(CharacterRange::IsCanonical(&l2));
1803
1804   ZoneList<CharacterRange> first_only(4, &zone);
1805   ZoneList<CharacterRange> second_only(4, &zone);
1806   ZoneList<CharacterRange> both(4, &zone);
1807 }
1808
1809
1810 TEST(Graph) {
1811   V8::Initialize(NULL);
1812   Execute("\\b\\w+\\b", false, true, true);
1813 }