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

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