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