test-regexp.cc 68.2 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

28
#include <cstdlib>
29
#include <memory>
30
#include <sstream>
31

32
#include "include/v8.h"
33
#include "src/v8.h"
34

35
#include "src/api-inl.h"
36
#include "src/ast/ast.h"
37
#include "src/char-predicates-inl.h"
38
#include "src/objects-inl.h"
39
#include "src/ostreams.h"
40 41
#include "src/regexp/jsregexp.h"
#include "src/regexp/regexp-macro-assembler-irregexp.h"
42
#include "src/regexp/regexp-macro-assembler.h"
43
#include "src/regexp/regexp-parser.h"
44
#include "src/splay-tree-inl.h"
45
#include "src/string-stream.h"
46 47
#include "src/unicode-inl.h"

48
#ifdef V8_INTERPRETED_REGEXP
49
#include "src/regexp/interpreter-irregexp.h"
50
#else  // V8_INTERPRETED_REGEXP
51
#include "src/macro-assembler.h"
52
#if V8_TARGET_ARCH_ARM
53
#include "src/arm/assembler-arm.h"  // NOLINT
54
#include "src/arm/macro-assembler-arm.h"
55
#include "src/regexp/arm/regexp-macro-assembler-arm.h"
56
#endif
57
#if V8_TARGET_ARCH_ARM64
58 59
#include "src/arm64/assembler-arm64.h"
#include "src/arm64/macro-assembler-arm64.h"
60
#include "src/regexp/arm64/regexp-macro-assembler-arm64.h"
61
#endif
62 63 64 65 66
#if V8_TARGET_ARCH_S390
#include "src/regexp/s390/regexp-macro-assembler-s390.h"
#include "src/s390/assembler-s390.h"
#include "src/s390/macro-assembler-s390.h"
#endif
67 68 69
#if V8_TARGET_ARCH_PPC
#include "src/ppc/assembler-ppc.h"
#include "src/ppc/macro-assembler-ppc.h"
70
#include "src/regexp/ppc/regexp-macro-assembler-ppc.h"
71
#endif
72
#if V8_TARGET_ARCH_MIPS
73 74
#include "src/mips/assembler-mips.h"
#include "src/mips/macro-assembler-mips.h"
75
#include "src/regexp/mips/regexp-macro-assembler-mips.h"
76
#endif
77 78 79
#if V8_TARGET_ARCH_MIPS64
#include "src/mips64/assembler-mips64.h"
#include "src/mips64/macro-assembler-mips64.h"
80
#include "src/regexp/mips64/regexp-macro-assembler-mips64.h"
81
#endif
82
#if V8_TARGET_ARCH_X64
83
#include "src/regexp/x64/regexp-macro-assembler-x64.h"
84 85
#include "src/x64/assembler-x64.h"
#include "src/x64/macro-assembler-x64.h"
86
#endif
87
#if V8_TARGET_ARCH_IA32
88 89
#include "src/ia32/assembler-ia32.h"
#include "src/ia32/macro-assembler-ia32.h"
90
#include "src/regexp/ia32/regexp-macro-assembler-ia32.h"
91
#endif
92
#endif  // V8_INTERPRETED_REGEXP
93
#include "test/cctest/cctest.h"
94

95 96
namespace v8 {
namespace internal {
97
namespace test_regexp {
98

99
static bool CheckParse(const char* input) {
100
  v8::HandleScope scope(CcTest::isolate());
101
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
102
  FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
103
  RegExpCompileData result;
104
  return v8::internal::RegExpParser::ParseRegExp(
105
      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result);
106 107 108
}


109 110
static void CheckParseEq(const char* input, const char* expected,
                         bool unicode = false) {
111
  v8::HandleScope scope(CcTest::isolate());
112
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
113
  FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
114
  RegExpCompileData result;
115 116 117 118
  JSRegExp::Flags flags = JSRegExp::kNone;
  if (unicode) flags |= JSRegExp::kUnicode;
  CHECK(v8::internal::RegExpParser::ParseRegExp(CcTest::i_isolate(), &zone,
                                                &reader, flags, &result));
119
  CHECK_NOT_NULL(result.tree);
120
  CHECK(result.error.is_null());
121
  std::ostringstream os;
122
  result.tree->Print(os, &zone);
123 124 125
  if (strcmp(expected, os.str().c_str()) != 0) {
    printf("%s | %s\n", expected, os.str().c_str());
  }
126
  CHECK_EQ(0, strcmp(expected, os.str().c_str()));
127 128
}

129

130
static bool CheckSimple(const char* input) {
131
  v8::HandleScope scope(CcTest::isolate());
132
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
133
  FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
134
  RegExpCompileData result;
135
  CHECK(v8::internal::RegExpParser::ParseRegExp(
136
      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result));
137
  CHECK_NOT_NULL(result.tree);
138
  CHECK(result.error.is_null());
139
  return result.simple;
140 141
}

142 143 144 145 146
struct MinMaxPair {
  int min_match;
  int max_match;
};

147

148
static MinMaxPair CheckMinMaxMatch(const char* input) {
149
  v8::HandleScope scope(CcTest::isolate());
150
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
151
  FlatStringReader reader(CcTest::i_isolate(), CStrVector(input));
152
  RegExpCompileData result;
153
  CHECK(v8::internal::RegExpParser::ParseRegExp(
154
      CcTest::i_isolate(), &zone, &reader, JSRegExp::kNone, &result));
155
  CHECK_NOT_NULL(result.tree);
156 157 158 159 160 161 162 163
  CHECK(result.error.is_null());
  int min_match = result.tree->min_match();
  int max_match = result.tree->max_match();
  MinMaxPair pair = { min_match, max_match };
  return pair;
}


164
#define CHECK_PARSE_ERROR(input) CHECK(!CheckParse(input))
165
#define CHECK_SIMPLE(input, simple) CHECK_EQ(simple, CheckSimple(input));
166 167 168 169 170
#define CHECK_MIN_MAX(input, min, max)                                         \
  { MinMaxPair min_max = CheckMinMaxMatch(input);                              \
    CHECK_EQ(min, min_max.min_match);                                          \
    CHECK_EQ(max, min_max.max_match);                                          \
  }
171

172
TEST(RegExpParser) {
173 174
  CHECK_PARSE_ERROR("?");

175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
  CheckParseEq("abc", "'abc'");
  CheckParseEq("", "%");
  CheckParseEq("abc|def", "(| 'abc' 'def')");
  CheckParseEq("abc|def|ghi", "(| 'abc' 'def' 'ghi')");
  CheckParseEq("^xxx$", "(: @^i 'xxx' @$i)");
  CheckParseEq("ab\\b\\d\\bcd", "(: 'ab' @b [0-9] @b 'cd')");
  CheckParseEq("\\w|\\d", "(| [0-9 A-Z _ a-z] [0-9])");
  CheckParseEq("a*", "(# 0 - g 'a')");
  CheckParseEq("a*?", "(# 0 - n 'a')");
  CheckParseEq("abc+", "(: 'ab' (# 1 - g 'c'))");
  CheckParseEq("abc+?", "(: 'ab' (# 1 - n 'c'))");
  CheckParseEq("xyz?", "(: 'xy' (# 0 1 g 'z'))");
  CheckParseEq("xyz??", "(: 'xy' (# 0 1 n 'z'))");
  CheckParseEq("xyz{0,1}", "(: 'xy' (# 0 1 g 'z'))");
  CheckParseEq("xyz{0,1}?", "(: 'xy' (# 0 1 n 'z'))");
  CheckParseEq("xyz{93}", "(: 'xy' (# 93 93 g 'z'))");
  CheckParseEq("xyz{93}?", "(: 'xy' (# 93 93 n 'z'))");
  CheckParseEq("xyz{1,32}", "(: 'xy' (# 1 32 g 'z'))");
  CheckParseEq("xyz{1,32}?", "(: 'xy' (# 1 32 n 'z'))");
  CheckParseEq("xyz{1,}", "(: 'xy' (# 1 - g 'z'))");
  CheckParseEq("xyz{1,}?", "(: 'xy' (# 1 - n 'z'))");
  CheckParseEq("a\\fb\\nc\\rd\\te\\vf", "'a\\x0cb\\x0ac\\x0dd\\x09e\\x0bf'");
  CheckParseEq("a\\nb\\bc", "(: 'a\\x0ab' @b 'c')");
198 199
  CheckParseEq("(?:foo)", "(?: 'foo')");
  CheckParseEq("(?: foo )", "(?: ' foo ')");
200 201 202 203
  CheckParseEq("(foo|bar|baz)", "(^ (| 'foo' 'bar' 'baz'))");
  CheckParseEq("foo|(bar|baz)|quux", "(| 'foo' (^ (| 'bar' 'baz')) 'quux')");
  CheckParseEq("foo(?=bar)baz", "(: 'foo' (-> + 'bar') 'baz')");
  CheckParseEq("foo(?!bar)baz", "(: 'foo' (-> - 'bar') 'baz')");
204 205
  CheckParseEq("foo(?<=bar)baz", "(: 'foo' (<- + 'bar') 'baz')");
  CheckParseEq("foo(?<!bar)baz", "(: 'foo' (<- - 'bar') 'baz')");
206 207
  CheckParseEq("()", "(^ %)");
  CheckParseEq("(?=)", "(-> + %)");
208 209
  CheckParseEq("[]", "^[\\x00-\\u{10ffff}]");  // Doesn't compile on windows
  CheckParseEq("[^]", "[\\x00-\\u{10ffff}]");  // \uffff isn't in codepage 1252
210 211 212 213 214 215 216 217 218 219 220
  CheckParseEq("[x]", "[x]");
  CheckParseEq("[xyz]", "[x y z]");
  CheckParseEq("[a-zA-Z0-9]", "[a-z A-Z 0-9]");
  CheckParseEq("[-123]", "[- 1 2 3]");
  CheckParseEq("[^123]", "^[1 2 3]");
  CheckParseEq("]", "']'");
  CheckParseEq("}", "'}'");
  CheckParseEq("[a-b-c]", "[a-b - c]");
  CheckParseEq("[\\d]", "[0-9]");
  CheckParseEq("[x\\dz]", "[x 0-9 z]");
  CheckParseEq("[\\d-z]", "[0-9 - z]");
221 222
  CheckParseEq("[\\d-\\d]", "[0-9 0-9 -]");
  CheckParseEq("[z-\\d]", "[0-9 z -]");
223
  // Control character outside character class.
224 225 226 227 228
  CheckParseEq("\\cj\\cJ\\ci\\cI\\ck\\cK", "'\\x0a\\x0a\\x09\\x09\\x0b\\x0b'");
  CheckParseEq("\\c!", "'\\c!'");
  CheckParseEq("\\c_", "'\\c_'");
  CheckParseEq("\\c~", "'\\c~'");
  CheckParseEq("\\c1", "'\\c1'");
229
  // Control character inside character class.
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276
  CheckParseEq("[\\c!]", "[\\ c !]");
  CheckParseEq("[\\c_]", "[\\x1f]");
  CheckParseEq("[\\c~]", "[\\ c ~]");
  CheckParseEq("[\\ca]", "[\\x01]");
  CheckParseEq("[\\cz]", "[\\x1a]");
  CheckParseEq("[\\cA]", "[\\x01]");
  CheckParseEq("[\\cZ]", "[\\x1a]");
  CheckParseEq("[\\c1]", "[\\x11]");

  CheckParseEq("[a\\]c]", "[a ] c]");
  CheckParseEq("\\[\\]\\{\\}\\(\\)\\%\\^\\#\\ ", "'[]{}()%^# '");
  CheckParseEq("[\\[\\]\\{\\}\\(\\)\\%\\^\\#\\ ]", "[[ ] { } ( ) % ^ #  ]");
  CheckParseEq("\\0", "'\\x00'");
  CheckParseEq("\\8", "'8'");
  CheckParseEq("\\9", "'9'");
  CheckParseEq("\\11", "'\\x09'");
  CheckParseEq("\\11a", "'\\x09a'");
  CheckParseEq("\\011", "'\\x09'");
  CheckParseEq("\\00011", "'\\x0011'");
  CheckParseEq("\\118", "'\\x098'");
  CheckParseEq("\\111", "'I'");
  CheckParseEq("\\1111", "'I1'");
  CheckParseEq("(x)(x)(x)\\1", "(: (^ 'x') (^ 'x') (^ 'x') (<- 1))");
  CheckParseEq("(x)(x)(x)\\2", "(: (^ 'x') (^ 'x') (^ 'x') (<- 2))");
  CheckParseEq("(x)(x)(x)\\3", "(: (^ 'x') (^ 'x') (^ 'x') (<- 3))");
  CheckParseEq("(x)(x)(x)\\4", "(: (^ 'x') (^ 'x') (^ 'x') '\\x04')");
  CheckParseEq("(x)(x)(x)\\1*",
               "(: (^ 'x') (^ 'x') (^ 'x')"
               " (# 0 - g (<- 1)))");
  CheckParseEq("(x)(x)(x)\\2*",
               "(: (^ 'x') (^ 'x') (^ 'x')"
               " (# 0 - g (<- 2)))");
  CheckParseEq("(x)(x)(x)\\3*",
               "(: (^ 'x') (^ 'x') (^ 'x')"
               " (# 0 - g (<- 3)))");
  CheckParseEq("(x)(x)(x)\\4*",
               "(: (^ 'x') (^ 'x') (^ 'x')"
               " (# 0 - g '\\x04'))");
  CheckParseEq("(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)\\10",
               "(: (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x')"
               " (^ 'x') (^ 'x') (^ 'x') (^ 'x') (<- 10))");
  CheckParseEq("(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)\\11",
               "(: (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x')"
               " (^ 'x') (^ 'x') (^ 'x') (^ 'x') '\\x09')");
  CheckParseEq("(a)\\1", "(: (^ 'a') (<- 1))");
  CheckParseEq("(a\\1)", "(^ 'a')");
  CheckParseEq("(\\1a)", "(^ 'a')");
277
  CheckParseEq("(\\2)(\\1)", "(: (^ (<- 2)) (^ (<- 1)))");
278 279 280 281 282
  CheckParseEq("(?=a)?a", "'a'");
  CheckParseEq("(?=a){0,10}a", "'a'");
  CheckParseEq("(?=a){1,10}a", "(: (-> + 'a') 'a')");
  CheckParseEq("(?=a){9,10}a", "(: (-> + 'a') 'a')");
  CheckParseEq("(?!a)?a", "'a'");
283
  CheckParseEq("\\1(a)", "(: (<- 1) (^ 'a'))");
284
  CheckParseEq("(?!(a))\\1", "(: (-> - (^ 'a')) (<- 1))");
285 286 287
  CheckParseEq("(?!\\1(a\\1)\\1)\\1",
               "(: (-> - (: (<- 1) (^ 'a') (<- 1))) (<- 1))");
  CheckParseEq("\\1\\2(a(?:\\1(b\\1\\2))\\2)\\1",
288
               "(: (<- 1) (<- 2) (^ (: 'a' (?: (^ 'b')) (<- 2))) (<- 1))");
289 290
  CheckParseEq("\\1\\2(a(?<=\\1(b\\1\\2))\\2)\\1",
               "(: (<- 1) (<- 2) (^ (: 'a' (<- + (^ 'b')) (<- 2))) (<- 1))");
291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
  CheckParseEq("[\\0]", "[\\x00]");
  CheckParseEq("[\\11]", "[\\x09]");
  CheckParseEq("[\\11a]", "[\\x09 a]");
  CheckParseEq("[\\011]", "[\\x09]");
  CheckParseEq("[\\00011]", "[\\x00 1 1]");
  CheckParseEq("[\\118]", "[\\x09 8]");
  CheckParseEq("[\\111]", "[I]");
  CheckParseEq("[\\1111]", "[I 1]");
  CheckParseEq("\\x34", "'\x34'");
  CheckParseEq("\\x60", "'\x60'");
  CheckParseEq("\\x3z", "'x3z'");
  CheckParseEq("\\c", "'\\c'");
  CheckParseEq("\\u0034", "'\x34'");
  CheckParseEq("\\u003z", "'u003z'");
  CheckParseEq("foo[z]*", "(: 'foo' (# 0 - g [z]))");
306 307 308
  CheckParseEq("^^^$$$\\b\\b\\b\\b", "(: @^i @$i @b)");
  CheckParseEq("\\b\\b\\b\\b\\B\\B\\B\\B\\b\\b\\b\\b", "(: @b @B @b)");
  CheckParseEq("\\b\\B\\b", "(: @b @B @b)");
309

310 311
  // Unicode regexps
  CheckParseEq("\\u{12345}", "'\\ud808\\udf45'", true);
312 313
  CheckParseEq("\\u{12345}\\u{23456}", "(! '\\ud808\\udf45' '\\ud84d\\udc56')",
               true);
314 315
  CheckParseEq("\\u{12345}|\\u{23456}", "(| '\\ud808\\udf45' '\\ud84d\\udc56')",
               true);
316 317
  CheckParseEq("\\u{12345}{3}", "(# 3 3 g '\\ud808\\udf45')", true);
  CheckParseEq("\\u{12345}*", "(# 0 - g '\\ud808\\udf45')", true);
318

319 320 321 322
  CheckParseEq("\\ud808\\udf45*", "(# 0 - g '\\ud808\\udf45')", true);
  CheckParseEq("[\\ud808\\udf45-\\ud809\\udccc]", "[\\u{012345}-\\u{0124cc}]",
               true);

323
  CHECK_SIMPLE("", false);
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367
  CHECK_SIMPLE("a", true);
  CHECK_SIMPLE("a|b", false);
  CHECK_SIMPLE("a\\n", false);
  CHECK_SIMPLE("^a", false);
  CHECK_SIMPLE("a$", false);
  CHECK_SIMPLE("a\\b!", false);
  CHECK_SIMPLE("a\\Bb", false);
  CHECK_SIMPLE("a*", false);
  CHECK_SIMPLE("a*?", false);
  CHECK_SIMPLE("a?", false);
  CHECK_SIMPLE("a??", false);
  CHECK_SIMPLE("a{0,1}?", false);
  CHECK_SIMPLE("a{1,1}?", false);
  CHECK_SIMPLE("a{1,2}?", false);
  CHECK_SIMPLE("a+?", false);
  CHECK_SIMPLE("(a)", false);
  CHECK_SIMPLE("(a)\\1", false);
  CHECK_SIMPLE("(\\1a)", false);
  CHECK_SIMPLE("\\1(a)", false);
  CHECK_SIMPLE("a\\s", false);
  CHECK_SIMPLE("a\\S", false);
  CHECK_SIMPLE("a\\d", false);
  CHECK_SIMPLE("a\\D", false);
  CHECK_SIMPLE("a\\w", false);
  CHECK_SIMPLE("a\\W", false);
  CHECK_SIMPLE("a.", false);
  CHECK_SIMPLE("a\\q", false);
  CHECK_SIMPLE("a[a]", false);
  CHECK_SIMPLE("a[^a]", false);
  CHECK_SIMPLE("a[a-z]", false);
  CHECK_SIMPLE("a[\\q]", false);
  CHECK_SIMPLE("a(?:b)", false);
  CHECK_SIMPLE("a(?=b)", false);
  CHECK_SIMPLE("a(?!b)", false);
  CHECK_SIMPLE("\\x60", false);
  CHECK_SIMPLE("\\u0060", false);
  CHECK_SIMPLE("\\cA", false);
  CHECK_SIMPLE("\\q", false);
  CHECK_SIMPLE("\\1112", false);
  CHECK_SIMPLE("\\0", false);
  CHECK_SIMPLE("(a)\\1", false);
  CHECK_SIMPLE("(?=a)?a", false);
  CHECK_SIMPLE("(?!a)?a\\1", false);
  CHECK_SIMPLE("(?:(?=a))a\\1", false);
368

369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384
  CheckParseEq("a{}", "'a{}'");
  CheckParseEq("a{,}", "'a{,}'");
  CheckParseEq("a{", "'a{'");
  CheckParseEq("a{z}", "'a{z}'");
  CheckParseEq("a{1z}", "'a{1z}'");
  CheckParseEq("a{12z}", "'a{12z}'");
  CheckParseEq("a{12,", "'a{12,'");
  CheckParseEq("a{12,3b", "'a{12,3b'");
  CheckParseEq("{}", "'{}'");
  CheckParseEq("{,}", "'{,}'");
  CheckParseEq("{", "'{'");
  CheckParseEq("{z}", "'{z}'");
  CheckParseEq("{1z}", "'{1z}'");
  CheckParseEq("{12z}", "'{12z}'");
  CheckParseEq("{12,", "'{12,'");
  CheckParseEq("{12,3b", "'{12,3b'");
385 386 387 388 389 390 391 392 393 394 395 396 397

  CHECK_MIN_MAX("a", 1, 1);
  CHECK_MIN_MAX("abc", 3, 3);
  CHECK_MIN_MAX("a[bc]d", 3, 3);
  CHECK_MIN_MAX("a|bc", 1, 2);
  CHECK_MIN_MAX("ab|c", 1, 2);
  CHECK_MIN_MAX("a||bc", 0, 2);
  CHECK_MIN_MAX("|", 0, 0);
  CHECK_MIN_MAX("(?:ab)", 2, 2);
  CHECK_MIN_MAX("(?:ab|cde)", 2, 3);
  CHECK_MIN_MAX("(?:ab)|cde", 2, 3);
  CHECK_MIN_MAX("(ab)", 2, 2);
  CHECK_MIN_MAX("(ab|cde)", 2, 3);
398 399
  CHECK_MIN_MAX("(ab)\\1", 2, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(ab|cde)\\1", 2, RegExpTree::kInfinity);
400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
  CHECK_MIN_MAX("(?:ab)?", 0, 2);
  CHECK_MIN_MAX("(?:ab)*", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:ab)+", 2, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a?", 0, 1);
  CHECK_MIN_MAX("a*", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a+", 1, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a??", 0, 1);
  CHECK_MIN_MAX("a*?", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a+?", 1, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a?)?", 0, 1);
  CHECK_MIN_MAX("(?:a*)?", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a+)?", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a?)+", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a*)+", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a+)+", 1, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a?)*", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a*)*", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a+)*", 0, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a{0}", 0, 0);
  CHECK_MIN_MAX("(?:a+){0}", 0, 0);
  CHECK_MIN_MAX("(?:a+){0,0}", 0, 0);
  CHECK_MIN_MAX("a*b", 1, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a+b", 2, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a*b|c", 1, RegExpTree::kInfinity);
  CHECK_MIN_MAX("a+b|c", 1, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:a{5,1000000}){3,1000000}", 15, RegExpTree::kInfinity);
  CHECK_MIN_MAX("(?:ab){4,7}", 8, 14);
  CHECK_MIN_MAX("a\\bc", 2, 2);
  CHECK_MIN_MAX("a\\Bc", 2, 2);
  CHECK_MIN_MAX("a\\sc", 3, 3);
  CHECK_MIN_MAX("a\\Sc", 3, 3);
  CHECK_MIN_MAX("a(?=b)c", 2, 2);
  CHECK_MIN_MAX("a(?=bbb|bb)c", 2, 2);
  CHECK_MIN_MAX("a(?!bbb|bb)c", 2, 2);
434 435 436 437 438 439 440 441 442 443 444 445 446 447 448

  CheckParseEq("(?<a>x)(?<b>x)(?<c>x)\\k<a>",
               "(: (^ 'x') (^ 'x') (^ 'x') (<- 1))", true);
  CheckParseEq("(?<a>x)(?<b>x)(?<c>x)\\k<b>",
               "(: (^ 'x') (^ 'x') (^ 'x') (<- 2))", true);
  CheckParseEq("(?<a>x)(?<b>x)(?<c>x)\\k<c>",
               "(: (^ 'x') (^ 'x') (^ 'x') (<- 3))", true);
  CheckParseEq("(?<a>a)\\k<a>", "(: (^ 'a') (<- 1))", true);
  CheckParseEq("(?<a>a\\k<a>)", "(^ 'a')", true);
  CheckParseEq("(?<a>\\k<a>a)", "(^ 'a')", true);
  CheckParseEq("(?<a>\\k<b>)(?<b>\\k<a>)", "(: (^ (<- 2)) (^ (<- 1)))", true);
  CheckParseEq("\\k<a>(?<a>a)", "(: (<- 1) (^ 'a'))", true);

  CheckParseEq("(?<\\u{03C0}>a)", "(^ 'a')", true);
  CheckParseEq("(?<\\u03C0>a)", "(^ 'a')", true);
449 450 451
}

TEST(ParserRegression) {
452 453 454 455
  CheckParseEq("[A-Z$-][x]", "(! [A-Z $ -] [x])");
  CheckParseEq("a{3,4*}", "(: 'a{3,' (# 0 - g '4') '}')");
  CheckParseEq("{", "'{'");
  CheckParseEq("a|", "(| 'a' %)");
456 457
}

458 459
static void ExpectError(const char* input, const char* expected,
                        bool unicode = false) {
460 461
  Isolate* isolate = CcTest::i_isolate();

462
  v8::HandleScope scope(CcTest::isolate());
463 464
  Zone zone(isolate->allocator(), ZONE_NAME);
  FlatStringReader reader(isolate, CStrVector(input));
465
  RegExpCompileData result;
466 467
  JSRegExp::Flags flags = JSRegExp::kNone;
  if (unicode) flags |= JSRegExp::kUnicode;
468 469
  CHECK(!v8::internal::RegExpParser::ParseRegExp(isolate, &zone, &reader, flags,
                                                 &result));
470
  CHECK_NULL(result.tree);
471
  CHECK(!result.error.is_null());
472
  std::unique_ptr<char[]> str = result.error->ToCString(ALLOW_NULLS);
473
  CHECK_EQ(0, strcmp(expected, str.get()));
474 475 476
}


477
TEST(Errors) {
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
  const char* kEndBackslash = "\\ at end of pattern";
  ExpectError("\\", kEndBackslash);
  const char* kUnterminatedGroup = "Unterminated group";
  ExpectError("(foo", kUnterminatedGroup);
  const char* kInvalidGroup = "Invalid group";
  ExpectError("(?", kInvalidGroup);
  const char* kUnterminatedCharacterClass = "Unterminated character class";
  ExpectError("[", kUnterminatedCharacterClass);
  ExpectError("[a-", kUnterminatedCharacterClass);
  const char* kNothingToRepeat = "Nothing to repeat";
  ExpectError("*", kNothingToRepeat);
  ExpectError("?", kNothingToRepeat);
  ExpectError("+", kNothingToRepeat);
  ExpectError("{1}", kNothingToRepeat);
  ExpectError("{1,2}", kNothingToRepeat);
  ExpectError("{1,}", kNothingToRepeat);
494 495 496 497

  // Check that we don't allow more than kMaxCapture captures
  const int kMaxCaptures = 1 << 16;  // Must match RegExpParser::kMaxCaptures.
  const char* kTooManyCaptures = "Too many captures";
498
  std::ostringstream os;
499
  for (int i = 0; i <= kMaxCaptures; i++) {
500
    os << "()";
501
  }
502
  ExpectError(os.str().c_str(), kTooManyCaptures);
503 504 505 506 507 508 509 510 511 512 513 514 515 516 517

  const char* kInvalidCaptureName = "Invalid capture group name";
  ExpectError("(?<>.)", kInvalidCaptureName, true);
  ExpectError("(?<1>.)", kInvalidCaptureName, true);
  ExpectError("(?<_%>.)", kInvalidCaptureName, true);
  ExpectError("\\k<a", kInvalidCaptureName, true);
  const char* kDuplicateCaptureName = "Duplicate capture group name";
  ExpectError("(?<a>.)(?<a>.)", kDuplicateCaptureName, true);
  const char* kInvalidUnicodeEscape = "Invalid Unicode escape sequence";
  ExpectError("(?<\\u{FISK}", kInvalidUnicodeEscape, true);
  const char* kInvalidCaptureReferenced = "Invalid named capture referenced";
  ExpectError("\\k<a>", kInvalidCaptureReferenced, true);
  ExpectError("(?<b>)\\k<a>", kInvalidCaptureReferenced, true);
  const char* kInvalidNamedReference = "Invalid named reference";
  ExpectError("\\ka", kInvalidNamedReference, true);
518 519 520 521 522 523 524 525 526 527 528 529 530
}


static bool IsDigit(uc16 c) {
  return ('0' <= c && c <= '9');
}


static bool NotDigit(uc16 c) {
  return !IsDigit(c);
}


531 532 533 534
static bool IsWhiteSpaceOrLineTerminator(uc16 c) {
  // According to ECMA 5.1, 15.10.2.12 the CharacterClassEscape \s includes
  // WhiteSpace (7.2) and LineTerminator (7.3) values.
  return v8::internal::WhiteSpaceOrLineTerminator::Is(c);
535 536 537
}


538 539
static bool NotWhiteSpaceNorLineTermiantor(uc16 c) {
  return !IsWhiteSpaceOrLineTerminator(c);
540 541 542 543
}


static bool NotWord(uc16 c) {
544
  return !IsRegExpWord(c);
545 546 547 548
}


static void TestCharacterClassEscapes(uc16 c, bool (pred)(uc16 c)) {
549
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
550
  ZoneList<CharacterRange>* ranges =
551 552
      new(&zone) ZoneList<CharacterRange>(2, &zone);
  CharacterRange::AddClassEscape(c, ranges, &zone);
553
  for (uc32 i = 0; i < (1 << 16); i++) {
554 555 556 557 558 559 560 561 562 563 564
    bool in_class = false;
    for (int j = 0; !in_class && j < ranges->length(); j++) {
      CharacterRange& range = ranges->at(j);
      in_class = (range.from() <= i && i <= range.to());
    }
    CHECK_EQ(pred(i), in_class);
  }
}


TEST(CharacterClassEscapes) {
565
  TestCharacterClassEscapes('.', IsRegExpNewline);
566 567
  TestCharacterClassEscapes('d', IsDigit);
  TestCharacterClassEscapes('D', NotDigit);
568 569
  TestCharacterClassEscapes('s', IsWhiteSpaceOrLineTerminator);
  TestCharacterClassEscapes('S', NotWhiteSpaceNorLineTermiantor);
570
  TestCharacterClassEscapes('w', IsRegExpWord);
571 572 573 574
  TestCharacterClassEscapes('W', NotWord);
}


575 576
static RegExpNode* Compile(const char* input, bool multiline, bool unicode,
                           bool is_one_byte, Zone* zone) {
577
  Isolate* isolate = CcTest::i_isolate();
578
  FlatStringReader reader(isolate, CStrVector(input));
579
  RegExpCompileData compile_data;
580 581 582
  JSRegExp::Flags flags = JSRegExp::kNone;
  if (multiline) flags = JSRegExp::kMultiline;
  if (unicode) flags = JSRegExp::kUnicode;
583
  if (!v8::internal::RegExpParser::ParseRegExp(CcTest::i_isolate(), zone,
584
                                               &reader, flags, &compile_data))
585
    return nullptr;
586 587 588
  Handle<String> pattern = isolate->factory()
                               ->NewStringFromUtf8(CStrVector(input))
                               .ToHandleChecked();
589
  Handle<String> sample_subject =
590
      isolate->factory()->NewStringFromUtf8(CStrVector("")).ToHandleChecked();
591 592
  RegExpEngine::Compile(isolate, zone, &compile_data, flags, pattern,
                        sample_subject, is_one_byte);
593
  return compile_data.node;
594 595 596
}


597 598
static void Execute(const char* input, bool multiline, bool unicode,
                    bool is_one_byte, bool dot_output = false) {
599
  v8::HandleScope scope(CcTest::isolate());
600
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
601
  RegExpNode* node = Compile(input, multiline, unicode, is_one_byte, &zone);
602 603 604
  USE(node);
#ifdef DEBUG
  if (dot_output) {
605
    RegExpEngine::DotPrint(input, node, false);
606 607 608 609 610 611 612 613 614 615
  }
#endif  // DEBUG
}


class TestConfig {
 public:
  typedef int Key;
  typedef int Value;
  static const int kNoKey;
616
  static int NoValue() { return 0; }
617 618 619 620 621 622 623 624 625 626 627 628 629 630
  static inline int Compare(int a, int b) {
    if (a < b)
      return -1;
    else if (a > b)
      return 1;
    else
      return 0;
  }
};


const int TestConfig::kNoKey = 0;


631
static unsigned PseudoRandom(int i, int j) {
632 633 634 635 636
  return ~(~((i * 781) ^ (j * 329)));
}


TEST(SplayTreeSimple) {
637
  static const unsigned kLimit = 1000;
638
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
639
  ZoneSplayTree<TestConfig> tree(&zone);
640 641
  bool seen[kLimit];
  for (unsigned i = 0; i < kLimit; i++) seen[i] = false;
642
#define CHECK_MAPS_EQUAL() do {                                      \
643 644
    for (unsigned k = 0; k < kLimit; k++)                            \
      CHECK_EQ(seen[k], tree.Find(k, &loc));                         \
645 646 647
  } while (false)
  for (int i = 0; i < 50; i++) {
    for (int j = 0; j < 50; j++) {
648
      int next = PseudoRandom(i, j) % kLimit;
649
      if (seen[next]) {
650 651 652 653 654 655 656
        // We've already seen this one.  Check the value and remove
        // it.
        ZoneSplayTree<TestConfig>::Locator loc;
        CHECK(tree.Find(next, &loc));
        CHECK_EQ(next, loc.key());
        CHECK_EQ(3 * next, loc.value());
        tree.Remove(next);
657
        seen[next] = false;
658 659 660 661 662 663 664 665
        CHECK_MAPS_EQUAL();
      } else {
        // Check that it wasn't there already and then add it.
        ZoneSplayTree<TestConfig>::Locator loc;
        CHECK(!tree.Find(next, &loc));
        CHECK(tree.Insert(next, &loc));
        CHECK_EQ(next, loc.key());
        loc.set_value(3 * next);
666
        seen[next] = true;
667 668 669
        CHECK_MAPS_EQUAL();
      }
      int val = PseudoRandom(j, i) % kLimit;
670 671 672 673 674
      if (seen[val]) {
        ZoneSplayTree<TestConfig>::Locator loc;
        CHECK(tree.FindGreatestLessThan(val, &loc));
        CHECK_EQ(loc.key(), val);
        break;
675 676
      }
      val = PseudoRandom(i + j, i - j) % kLimit;
677 678 679 680 681
      if (seen[val]) {
        ZoneSplayTree<TestConfig>::Locator loc;
        CHECK(tree.FindLeastGreaterThan(val, &loc));
        CHECK_EQ(loc.key(), val);
        break;
682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704
      }
    }
  }
}


TEST(DispatchTableConstruction) {
  // Initialize test data.
  static const int kLimit = 1000;
  static const int kRangeCount = 8;
  static const int kRangeSize = 16;
  uc16 ranges[kRangeCount][2 * kRangeSize];
  for (int i = 0; i < kRangeCount; i++) {
    Vector<uc16> range(ranges[i], 2 * kRangeSize);
    for (int j = 0; j < 2 * kRangeSize; j++) {
      range[j] = PseudoRandom(i + 25, j + 87) % kLimit;
    }
    range.Sort();
    for (int j = 1; j < 2 * kRangeSize; j++) {
      CHECK(range[j-1] <= range[j]);
    }
  }
  // Enter test data into dispatch table.
705
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
706
  DispatchTable table(&zone);
707 708 709
  for (int i = 0; i < kRangeCount; i++) {
    uc16* range = ranges[i];
    for (int j = 0; j < 2 * kRangeSize; j += 2)
710
      table.AddRange(CharacterRange::Range(range[j], range[j + 1]), i, &zone);
711 712 713 714 715 716 717 718 719 720 721 722 723 724
  }
  // Check that the table looks as we would expect
  for (int p = 0; p < kLimit; p++) {
    OutSet* outs = table.Get(p);
    for (int j = 0; j < kRangeCount; j++) {
      uc16* range = ranges[j];
      bool is_on = false;
      for (int k = 0; !is_on && (k < 2 * kRangeSize); k += 2)
        is_on = (range[k] <= p && p <= range[k + 1]);
      CHECK_EQ(is_on, outs->Get(j));
    }
  }
}

725

726 727 728 729 730 731 732 733 734
// Test of debug-only syntax.
#ifdef DEBUG

TEST(ParsePossessiveRepetition) {
  bool old_flag_value = FLAG_regexp_possessive_quantifier;

  // Enable possessive quantifier syntax.
  FLAG_regexp_possessive_quantifier = true;

735 736 737 738 739
  CheckParseEq("a*+", "(# 0 - p 'a')");
  CheckParseEq("a++", "(# 1 - p 'a')");
  CheckParseEq("a?+", "(# 0 1 p 'a')");
  CheckParseEq("a{10,20}+", "(# 10 20 p 'a')");
  CheckParseEq("za{10,20}+b", "(: 'z' (# 10 20 p 'a') 'b')");
740 741 742 743 744 745 746 747 748 749 750 751 752 753

  // Disable possessive quantifier syntax.
  FLAG_regexp_possessive_quantifier = false;

  CHECK_PARSE_ERROR("a*+");
  CHECK_PARSE_ERROR("a++");
  CHECK_PARSE_ERROR("a?+");
  CHECK_PARSE_ERROR("a{10,20}+");
  CHECK_PARSE_ERROR("a{10,20}+b");

  FLAG_regexp_possessive_quantifier = old_flag_value;
}

#endif
754

755 756
// Tests of interpreter.

757

758
#ifndef V8_INTERPRETED_REGEXP
759

lrn@chromium.org's avatar
lrn@chromium.org committed
760
#if V8_TARGET_ARCH_IA32
761
typedef RegExpMacroAssemblerIA32 ArchRegExpMacroAssembler;
lrn@chromium.org's avatar
lrn@chromium.org committed
762
#elif V8_TARGET_ARCH_X64
763
typedef RegExpMacroAssemblerX64 ArchRegExpMacroAssembler;
lrn@chromium.org's avatar
lrn@chromium.org committed
764 765
#elif V8_TARGET_ARCH_ARM
typedef RegExpMacroAssemblerARM ArchRegExpMacroAssembler;
766 767
#elif V8_TARGET_ARCH_ARM64
typedef RegExpMacroAssemblerARM64 ArchRegExpMacroAssembler;
768 769
#elif V8_TARGET_ARCH_S390
typedef RegExpMacroAssemblerS390 ArchRegExpMacroAssembler;
770 771
#elif V8_TARGET_ARCH_PPC
typedef RegExpMacroAssemblerPPC ArchRegExpMacroAssembler;
772
#elif V8_TARGET_ARCH_MIPS
773
typedef RegExpMacroAssemblerMIPS ArchRegExpMacroAssembler;
774 775
#elif V8_TARGET_ARCH_MIPS64
typedef RegExpMacroAssemblerMIPS ArchRegExpMacroAssembler;
danno@chromium.org's avatar
danno@chromium.org committed
776 777
#elif V8_TARGET_ARCH_X87
typedef RegExpMacroAssemblerX87 ArchRegExpMacroAssembler;
778 779
#endif

780 781
class ContextInitializer {
 public:
782
  ContextInitializer()
783 784
      : scope_(CcTest::isolate()),
        env_(v8::Context::New(CcTest::isolate())) {
785 786 787 788 789 790 791
    env_->Enter();
  }
  ~ContextInitializer() {
    env_->Exit();
  }
 private:
  v8::HandleScope scope_;
792
  v8::Local<v8::Context> env_;
793 794
};

795
static ArchRegExpMacroAssembler::Result Execute(Code* code, String* input,
796
                                                int start_offset,
797 798
                                                Address input_start,
                                                Address input_end,
799
                                                int* captures) {
800
  return NativeRegExpMacroAssembler::Execute(
801 802
      code, input, start_offset, reinterpret_cast<byte*>(input_start),
      reinterpret_cast<byte*>(input_end), captures, 0, CcTest::i_isolate());
803 804
}

805

806
TEST(MacroAssemblerNativeSuccess) {
807
  v8::V8::Initialize();
808
  ContextInitializer initializer;
809
  Isolate* isolate = CcTest::i_isolate();
810
  Factory* factory = isolate->factory();
811
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
812

813 814
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             4);
815 816 817

  m.Succeed();

818
  Handle<String> source = factory->NewStringFromStaticChars("");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
819
  Handle<Object> code_object = m.GetCode(source);
820 821 822
  Handle<Code> code = Handle<Code>::cast(code_object);

  int captures[4] = {42, 37, 87, 117};
823
  Handle<String> input = factory->NewStringFromStaticChars("foofoo");
824
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
825
  Address start_adr = seq_input->GetCharsAddress();
826

827 828 829 830 831 832
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
              *input,
              0,
              start_adr,
              start_adr + seq_input->length(),
833
              captures);
834

835
  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
836 837 838 839 840 841 842
  CHECK_EQ(-1, captures[0]);
  CHECK_EQ(-1, captures[1]);
  CHECK_EQ(-1, captures[2]);
  CHECK_EQ(-1, captures[3]);
}


843
TEST(MacroAssemblerNativeSimple) {
844
  v8::V8::Initialize();
845
  ContextInitializer initializer;
846
  Isolate* isolate = CcTest::i_isolate();
847
  Factory* factory = isolate->factory();
848
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
849

850 851
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             4);
852

853 854
  Label fail, backtrack;
  m.PushBacktrack(&fail);
855 856 857 858 859 860 861
  m.CheckNotAtStart(0, nullptr);
  m.LoadCurrentCharacter(2, nullptr);
  m.CheckNotCharacter('o', nullptr);
  m.LoadCurrentCharacter(1, nullptr, false);
  m.CheckNotCharacter('o', nullptr);
  m.LoadCurrentCharacter(0, nullptr, false);
  m.CheckNotCharacter('f', nullptr);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
862
  m.WriteCurrentPositionToRegister(0, 0);
863
  m.WriteCurrentPositionToRegister(1, 3);
864
  m.AdvanceCurrentPosition(3);
865
  m.PushBacktrack(&backtrack);
866
  m.Succeed();
867 868
  m.Bind(&backtrack);
  m.Backtrack();
869 870 871
  m.Bind(&fail);
  m.Fail();

872
  Handle<String> source = factory->NewStringFromStaticChars("^foo");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
873
  Handle<Object> code_object = m.GetCode(source);
874 875 876
  Handle<Code> code = Handle<Code>::cast(code_object);

  int captures[4] = {42, 37, 87, 117};
877
  Handle<String> input = factory->NewStringFromStaticChars("foofoo");
878
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
879 880
  Address start_adr = seq_input->GetCharsAddress();

881 882 883 884 885 886
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
              *input,
              0,
              start_adr,
              start_adr + input->length(),
887
              captures);
888

889
  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
890 891 892 893 894
  CHECK_EQ(0, captures[0]);
  CHECK_EQ(3, captures[1]);
  CHECK_EQ(-1, captures[2]);
  CHECK_EQ(-1, captures[3]);

895
  input = factory->NewStringFromStaticChars("barbarbar");
896
  seq_input = Handle<SeqOneByteString>::cast(input);
897 898
  start_adr = seq_input->GetCharsAddress();

899 900 901 902 903
  result = Execute(*code,
                   *input,
                   0,
                   start_adr,
                   start_adr + input->length(),
904
                   captures);
905

906
  CHECK_EQ(NativeRegExpMacroAssembler::FAILURE, result);
907 908 909
}


910
TEST(MacroAssemblerNativeSimpleUC16) {
911
  v8::V8::Initialize();
912
  ContextInitializer initializer;
913
  Isolate* isolate = CcTest::i_isolate();
914
  Factory* factory = isolate->factory();
915
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
916

917 918
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::UC16,
                             4);
919

920 921
  Label fail, backtrack;
  m.PushBacktrack(&fail);
922 923 924 925 926 927 928
  m.CheckNotAtStart(0, nullptr);
  m.LoadCurrentCharacter(2, nullptr);
  m.CheckNotCharacter('o', nullptr);
  m.LoadCurrentCharacter(1, nullptr, false);
  m.CheckNotCharacter('o', nullptr);
  m.LoadCurrentCharacter(0, nullptr, false);
  m.CheckNotCharacter('f', nullptr);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
929
  m.WriteCurrentPositionToRegister(0, 0);
930
  m.WriteCurrentPositionToRegister(1, 3);
931
  m.AdvanceCurrentPosition(3);
932
  m.PushBacktrack(&backtrack);
933
  m.Succeed();
934 935
  m.Bind(&backtrack);
  m.Backtrack();
936 937 938
  m.Bind(&fail);
  m.Fail();

939
  Handle<String> source = factory->NewStringFromStaticChars("^foo");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
940
  Handle<Object> code_object = m.GetCode(source);
941 942 943
  Handle<Code> code = Handle<Code>::cast(code_object);

  int captures[4] = {42, 37, 87, 117};
944
  const uc16 input_data[6] = {'f', 'o', 'o', 'f', 'o',
945
                              static_cast<uc16>(0x2603)};
946 947
  Handle<String> input = factory->NewStringFromTwoByte(
      Vector<const uc16>(input_data, 6)).ToHandleChecked();
948 949 950
  Handle<SeqTwoByteString> seq_input = Handle<SeqTwoByteString>::cast(input);
  Address start_adr = seq_input->GetCharsAddress();

951 952 953 954 955 956
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
              *input,
              0,
              start_adr,
              start_adr + input->length(),
957
              captures);
958

959
  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
960 961 962 963 964
  CHECK_EQ(0, captures[0]);
  CHECK_EQ(3, captures[1]);
  CHECK_EQ(-1, captures[2]);
  CHECK_EQ(-1, captures[3]);

965
  const uc16 input_data2[9] = {'b', 'a', 'r', 'b', 'a', 'r', 'b', 'a',
966
                               static_cast<uc16>(0x2603)};
967 968
  input = factory->NewStringFromTwoByte(
      Vector<const uc16>(input_data2, 9)).ToHandleChecked();
969 970 971
  seq_input = Handle<SeqTwoByteString>::cast(input);
  start_adr = seq_input->GetCharsAddress();

972 973 974 975 976
  result = Execute(*code,
                   *input,
                   0,
                   start_adr,
                   start_adr + input->length() * 2,
977
                   captures);
978

979
  CHECK_EQ(NativeRegExpMacroAssembler::FAILURE, result);
980 981 982
}


983
TEST(MacroAssemblerNativeBacktrack) {
984
  v8::V8::Initialize();
985
  ContextInitializer initializer;
986
  Isolate* isolate = CcTest::i_isolate();
987
  Factory* factory = isolate->factory();
988
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
989

990 991
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             0);
992 993 994 995 996 997 998

  Label fail;
  Label backtrack;
  m.LoadCurrentCharacter(10, &fail);
  m.Succeed();
  m.Bind(&fail);
  m.PushBacktrack(&backtrack);
999
  m.LoadCurrentCharacter(10, nullptr);
1000 1001 1002 1003
  m.Succeed();
  m.Bind(&backtrack);
  m.Fail();

1004
  Handle<String> source = factory->NewStringFromStaticChars("..........");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1005
  Handle<Object> code_object = m.GetCode(source);
1006 1007
  Handle<Code> code = Handle<Code>::cast(code_object);

1008
  Handle<String> input = factory->NewStringFromStaticChars("foofoo");
1009
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1010 1011
  Address start_adr = seq_input->GetCharsAddress();

1012 1013
  NativeRegExpMacroAssembler::Result result = Execute(
      *code, *input, 0, start_adr, start_adr + input->length(), nullptr);
1014

1015
  CHECK_EQ(NativeRegExpMacroAssembler::FAILURE, result);
1016 1017
}

1018

1019
TEST(MacroAssemblerNativeBackReferenceLATIN1) {
1020
  v8::V8::Initialize();
1021
  ContextInitializer initializer;
1022
  Isolate* isolate = CcTest::i_isolate();
1023
  Factory* factory = isolate->factory();
1024
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1025

1026 1027
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             4);
1028

erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1029
  m.WriteCurrentPositionToRegister(0, 0);
1030
  m.AdvanceCurrentPosition(2);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1031
  m.WriteCurrentPositionToRegister(1, 0);
1032
  Label nomatch;
1033
  m.CheckNotBackReference(0, false, &nomatch);
1034 1035 1036 1037
  m.Fail();
  m.Bind(&nomatch);
  m.AdvanceCurrentPosition(2);
  Label missing_match;
1038
  m.CheckNotBackReference(0, false, &missing_match);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1039
  m.WriteCurrentPositionToRegister(2, 0);
1040 1041 1042 1043
  m.Succeed();
  m.Bind(&missing_match);
  m.Fail();

1044
  Handle<String> source = factory->NewStringFromStaticChars("^(..)..\1");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1045
  Handle<Object> code_object = m.GetCode(source);
1046 1047
  Handle<Code> code = Handle<Code>::cast(code_object);

1048
  Handle<String> input = factory->NewStringFromStaticChars("fooofo");
1049
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1050 1051
  Address start_adr = seq_input->GetCharsAddress();

lrn@chromium.org's avatar
lrn@chromium.org committed
1052
  int output[4];
1053 1054 1055 1056 1057 1058
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
              *input,
              0,
              start_adr,
              start_adr + input->length(),
1059
              output);
1060 1061

  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1062 1063 1064
  CHECK_EQ(0, output[0]);
  CHECK_EQ(2, output[1]);
  CHECK_EQ(6, output[2]);
lrn@chromium.org's avatar
lrn@chromium.org committed
1065
  CHECK_EQ(-1, output[3]);
1066 1067 1068
}


1069
TEST(MacroAssemblerNativeBackReferenceUC16) {
1070 1071
  v8::V8::Initialize();
  ContextInitializer initializer;
1072
  Isolate* isolate = CcTest::i_isolate();
1073
  Factory* factory = isolate->factory();
1074
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1075

1076 1077
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::UC16,
                             4);
1078 1079 1080 1081 1082

  m.WriteCurrentPositionToRegister(0, 0);
  m.AdvanceCurrentPosition(2);
  m.WriteCurrentPositionToRegister(1, 0);
  Label nomatch;
1083
  m.CheckNotBackReference(0, false, &nomatch);
1084 1085 1086 1087
  m.Fail();
  m.Bind(&nomatch);
  m.AdvanceCurrentPosition(2);
  Label missing_match;
1088
  m.CheckNotBackReference(0, false, &missing_match);
1089 1090 1091 1092 1093
  m.WriteCurrentPositionToRegister(2, 0);
  m.Succeed();
  m.Bind(&missing_match);
  m.Fail();

1094
  Handle<String> source = factory->NewStringFromStaticChars("^(..)..\1");
1095 1096 1097 1098
  Handle<Object> code_object = m.GetCode(source);
  Handle<Code> code = Handle<Code>::cast(code_object);

  const uc16 input_data[6] = {'f', 0x2028, 'o', 'o', 'f', 0x2028};
1099 1100
  Handle<String> input = factory->NewStringFromTwoByte(
      Vector<const uc16>(input_data, 6)).ToHandleChecked();
1101 1102 1103
  Handle<SeqTwoByteString> seq_input = Handle<SeqTwoByteString>::cast(input);
  Address start_adr = seq_input->GetCharsAddress();

lrn@chromium.org's avatar
lrn@chromium.org committed
1104
  int output[4];
1105 1106
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
1107 1108 1109 1110 1111
              *input,
              0,
              start_adr,
              start_adr + input->length() * 2,
              output);
1112

1113
  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1114 1115 1116
  CHECK_EQ(0, output[0]);
  CHECK_EQ(2, output[1]);
  CHECK_EQ(6, output[2]);
lrn@chromium.org's avatar
lrn@chromium.org committed
1117
  CHECK_EQ(-1, output[3]);
1118 1119 1120 1121
}



1122
TEST(MacroAssemblernativeAtStart) {
1123
  v8::V8::Initialize();
1124
  ContextInitializer initializer;
1125
  Isolate* isolate = CcTest::i_isolate();
1126
  Factory* factory = isolate->factory();
1127
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1128

1129 1130
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             0);
1131 1132

  Label not_at_start, newline, fail;
1133
  m.CheckNotAtStart(0, &not_at_start);
1134 1135 1136 1137 1138 1139 1140 1141
  // Check that prevchar = '\n' and current = 'f'.
  m.CheckCharacter('\n', &newline);
  m.Bind(&fail);
  m.Fail();
  m.Bind(&newline);
  m.LoadCurrentCharacter(0, &fail);
  m.CheckNotCharacter('f', &fail);
  m.Succeed();
1142

1143 1144 1145 1146 1147 1148 1149 1150 1151 1152
  m.Bind(&not_at_start);
  // Check that prevchar = 'o' and current = 'b'.
  Label prevo;
  m.CheckCharacter('o', &prevo);
  m.Fail();
  m.Bind(&prevo);
  m.LoadCurrentCharacter(0, &fail);
  m.CheckNotCharacter('b', &fail);
  m.Succeed();

1153
  Handle<String> source = factory->NewStringFromStaticChars("(^f|ob)");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1154
  Handle<Object> code_object = m.GetCode(source);
1155 1156
  Handle<Code> code = Handle<Code>::cast(code_object);

1157
  Handle<String> input = factory->NewStringFromStaticChars("foobar");
1158
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1159 1160
  Address start_adr = seq_input->GetCharsAddress();

1161 1162
  NativeRegExpMacroAssembler::Result result = Execute(
      *code, *input, 0, start_adr, start_adr + input->length(), nullptr);
1163 1164 1165

  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);

1166 1167
  result = Execute(*code, *input, 3, start_adr + 3, start_adr + input->length(),
                   nullptr);
1168 1169

  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1170 1171 1172
}


1173
TEST(MacroAssemblerNativeBackRefNoCase) {
1174
  v8::V8::Initialize();
1175
  ContextInitializer initializer;
1176
  Isolate* isolate = CcTest::i_isolate();
1177
  Factory* factory = isolate->factory();
1178
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1179

1180 1181
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             4);
1182 1183 1184

  Label fail, succ;

erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1185 1186
  m.WriteCurrentPositionToRegister(0, 0);
  m.WriteCurrentPositionToRegister(2, 0);
1187
  m.AdvanceCurrentPosition(3);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1188
  m.WriteCurrentPositionToRegister(3, 0);
1189 1190
  m.CheckNotBackReferenceIgnoreCase(2, false, false, &fail);  // Match "AbC".
  m.CheckNotBackReferenceIgnoreCase(2, false, false, &fail);  // Match "ABC".
1191
  Label expected_fail;
1192
  m.CheckNotBackReferenceIgnoreCase(2, false, false, &expected_fail);
1193 1194 1195 1196 1197
  m.Bind(&fail);
  m.Fail();

  m.Bind(&expected_fail);
  m.AdvanceCurrentPosition(3);  // Skip "xYz"
1198
  m.CheckNotBackReferenceIgnoreCase(2, false, false, &succ);
1199 1200 1201
  m.Fail();

  m.Bind(&succ);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1202
  m.WriteCurrentPositionToRegister(1, 0);
1203 1204
  m.Succeed();

erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1205
  Handle<String> source =
1206
      factory->NewStringFromStaticChars("^(abc)\1\1(?!\1)...(?!\1)");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1207
  Handle<Object> code_object = m.GetCode(source);
1208 1209
  Handle<Code> code = Handle<Code>::cast(code_object);

1210
  Handle<String> input = factory->NewStringFromStaticChars("aBcAbCABCxYzab");
1211
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1212 1213 1214
  Address start_adr = seq_input->GetCharsAddress();

  int output[4];
1215 1216 1217 1218 1219 1220
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
              *input,
              0,
              start_adr,
              start_adr + input->length(),
1221
              output);
1222 1223

  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1224 1225 1226 1227 1228 1229 1230 1231
  CHECK_EQ(0, output[0]);
  CHECK_EQ(12, output[1]);
  CHECK_EQ(0, output[2]);
  CHECK_EQ(3, output[3]);
}



1232
TEST(MacroAssemblerNativeRegisters) {
1233
  v8::V8::Initialize();
1234
  ContextInitializer initializer;
1235
  Isolate* isolate = CcTest::i_isolate();
1236
  Factory* factory = isolate->factory();
1237
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1238

1239 1240
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             6);
1241 1242 1243 1244

  uc16 foo_chars[3] = {'f', 'o', 'o'};
  Vector<const uc16> foo(foo_chars, 3);

lrn@chromium.org's avatar
lrn@chromium.org committed
1245
  enum registers { out1, out2, out3, out4, out5, out6, sp, loop_cnt };
1246 1247
  Label fail;
  Label backtrack;
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1248
  m.WriteCurrentPositionToRegister(out1, 0);  // Output: [0]
1249
  m.PushRegister(out1, RegExpMacroAssembler::kNoStackLimitCheck);
1250 1251 1252 1253
  m.PushBacktrack(&backtrack);
  m.WriteStackPointerToRegister(sp);
  // Fill stack and registers
  m.AdvanceCurrentPosition(2);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1254
  m.WriteCurrentPositionToRegister(out1, 0);
1255
  m.PushRegister(out1, RegExpMacroAssembler::kNoStackLimitCheck);
1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269
  m.PushBacktrack(&fail);
  // Drop backtrack stack frames.
  m.ReadStackPointerFromRegister(sp);
  // And take the first backtrack (to &backtrack)
  m.Backtrack();

  m.PushCurrentPosition();
  m.AdvanceCurrentPosition(2);
  m.PopCurrentPosition();

  m.Bind(&backtrack);
  m.PopRegister(out1);
  m.ReadCurrentPositionFromRegister(out1);
  m.AdvanceCurrentPosition(3);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1270
  m.WriteCurrentPositionToRegister(out2, 0);  // [0,3]
1271 1272 1273 1274 1275 1276 1277

  Label loop;
  m.SetRegister(loop_cnt, 0);  // loop counter
  m.Bind(&loop);
  m.AdvanceRegister(loop_cnt, 1);
  m.AdvanceCurrentPosition(1);
  m.IfRegisterLT(loop_cnt, 3, &loop);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1278
  m.WriteCurrentPositionToRegister(out3, 0);  // [0,3,6]
1279 1280 1281 1282 1283 1284 1285

  Label loop2;
  m.SetRegister(loop_cnt, 2);  // loop counter
  m.Bind(&loop2);
  m.AdvanceRegister(loop_cnt, -1);
  m.AdvanceCurrentPosition(1);
  m.IfRegisterGE(loop_cnt, 0, &loop2);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1286
  m.WriteCurrentPositionToRegister(out4, 0);  // [0,3,6,9]
1287 1288 1289

  Label loop3;
  Label exit_loop3;
1290 1291
  m.PushRegister(out4, RegExpMacroAssembler::kNoStackLimitCheck);
  m.PushRegister(out4, RegExpMacroAssembler::kNoStackLimitCheck);
1292 1293 1294
  m.ReadCurrentPositionFromRegister(out3);
  m.Bind(&loop3);
  m.AdvanceCurrentPosition(1);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1295
  m.CheckGreedyLoop(&exit_loop3);
1296 1297
  m.GoTo(&loop3);
  m.Bind(&exit_loop3);
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1298
  m.PopCurrentPosition();
lrn@chromium.org's avatar
lrn@chromium.org committed
1299
  m.WriteCurrentPositionToRegister(out5, 0);  // [0,3,6,9,9,-1]
1300 1301 1302 1303 1304 1305

  m.Succeed();

  m.Bind(&fail);
  m.Fail();

1306
  Handle<String> source = factory->NewStringFromStaticChars("<loop test>");
erik.corry@gmail.com's avatar
erik.corry@gmail.com committed
1307
  Handle<Object> code_object = m.GetCode(source);
1308 1309 1310
  Handle<Code> code = Handle<Code>::cast(code_object);

  // String long enough for test (content doesn't matter).
1311
  Handle<String> input = factory->NewStringFromStaticChars("foofoofoofoofoo");
1312
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1313 1314
  Address start_adr = seq_input->GetCharsAddress();

lrn@chromium.org's avatar
lrn@chromium.org committed
1315
  int output[6];
1316 1317
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
lrn@chromium.org's avatar
lrn@chromium.org committed
1318 1319 1320 1321
              *input,
              0,
              start_adr,
              start_adr + input->length(),
1322
              output);
1323

1324
  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1325 1326 1327 1328 1329
  CHECK_EQ(0, output[0]);
  CHECK_EQ(3, output[1]);
  CHECK_EQ(6, output[2]);
  CHECK_EQ(9, output[3]);
  CHECK_EQ(9, output[4]);
lrn@chromium.org's avatar
lrn@chromium.org committed
1330
  CHECK_EQ(-1, output[5]);
1331 1332
}

1333

1334
TEST(MacroAssemblerStackOverflow) {
1335
  v8::V8::Initialize();
1336
  ContextInitializer initializer;
1337
  Isolate* isolate = CcTest::i_isolate();
1338
  Factory* factory = isolate->factory();
1339
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1340

1341 1342
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             0);
1343 1344 1345 1346 1347 1348 1349

  Label loop;
  m.Bind(&loop);
  m.PushBacktrack(&loop);
  m.GoTo(&loop);

  Handle<String> source =
1350
      factory->NewStringFromStaticChars("<stack overflow test>");
1351 1352 1353 1354
  Handle<Object> code_object = m.GetCode(source);
  Handle<Code> code = Handle<Code>::cast(code_object);

  // String long enough for test (content doesn't matter).
1355
  Handle<String> input = factory->NewStringFromStaticChars("dummy");
1356
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1357 1358
  Address start_adr = seq_input->GetCharsAddress();

1359 1360
  NativeRegExpMacroAssembler::Result result = Execute(
      *code, *input, 0, start_adr, start_adr + input->length(), nullptr);
1361

1362
  CHECK_EQ(NativeRegExpMacroAssembler::EXCEPTION, result);
1363 1364
  CHECK(isolate->has_pending_exception());
  isolate->clear_pending_exception();
1365 1366 1367
}


1368
TEST(MacroAssemblerNativeLotsOfRegisters) {
1369 1370
  v8::V8::Initialize();
  ContextInitializer initializer;
1371
  Isolate* isolate = CcTest::i_isolate();
1372
  Factory* factory = isolate->factory();
1373
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1374

1375 1376
  ArchRegExpMacroAssembler m(isolate, &zone, NativeRegExpMacroAssembler::LATIN1,
                             2);
1377 1378 1379 1380 1381 1382 1383 1384

  // At least 2048, to ensure the allocated space for registers
  // span one full page.
  const int large_number = 8000;
  m.WriteCurrentPositionToRegister(large_number, 42);
  m.WriteCurrentPositionToRegister(0, 0);
  m.WriteCurrentPositionToRegister(1, 1);
  Label done;
1385
  m.CheckNotBackReference(0, false, &done);  // Performs a system-stack push.
1386 1387 1388 1389 1390 1391
  m.Bind(&done);
  m.PushRegister(large_number, RegExpMacroAssembler::kNoStackLimitCheck);
  m.PopRegister(1);
  m.Succeed();

  Handle<String> source =
1392
      factory->NewStringFromStaticChars("<huge register space test>");
1393 1394 1395 1396
  Handle<Object> code_object = m.GetCode(source);
  Handle<Code> code = Handle<Code>::cast(code_object);

  // String long enough for test (content doesn't matter).
1397
  Handle<String> input = factory->NewStringFromStaticChars("sample text");
1398
  Handle<SeqOneByteString> seq_input = Handle<SeqOneByteString>::cast(input);
1399 1400 1401
  Address start_adr = seq_input->GetCharsAddress();

  int captures[2];
1402 1403 1404 1405 1406 1407
  NativeRegExpMacroAssembler::Result result =
      Execute(*code,
              *input,
              0,
              start_adr,
              start_adr + input->length(),
1408
              captures);
1409 1410

  CHECK_EQ(NativeRegExpMacroAssembler::SUCCESS, result);
1411 1412 1413
  CHECK_EQ(0, captures[0]);
  CHECK_EQ(42, captures[1]);

1414
  isolate->clear_pending_exception();
1415 1416
}

1417
#else  // V8_INTERPRETED_REGEXP
1418 1419 1420

TEST(MacroAssembler) {
  byte codes[1024];
1421
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1422 1423
  RegExpMacroAssemblerIrregexp m(CcTest::i_isolate(), Vector<byte>(codes, 1024),
                                 &zone);
1424
  // ^f(o)o.
1425 1426
  Label start, fail, backtrack;

1427 1428 1429 1430 1431 1432
  m.SetRegister(4, 42);
  m.PushRegister(4, RegExpMacroAssembler::kNoStackLimitCheck);
  m.AdvanceRegister(4, 42);
  m.GoTo(&start);
  m.Fail();
  m.Bind(&start);
1433
  m.PushBacktrack(&fail);
1434 1435 1436 1437 1438 1439 1440
  m.CheckNotAtStart(0, nullptr);
  m.LoadCurrentCharacter(0, nullptr);
  m.CheckNotCharacter('f', nullptr);
  m.LoadCurrentCharacter(1, nullptr);
  m.CheckNotCharacter('o', nullptr);
  m.LoadCurrentCharacter(2, nullptr);
  m.CheckNotCharacter('o', nullptr);
1441
  m.WriteCurrentPositionToRegister(0, 0);
1442 1443 1444
  m.WriteCurrentPositionToRegister(1, 3);
  m.WriteCurrentPositionToRegister(2, 1);
  m.WriteCurrentPositionToRegister(3, 2);
1445
  m.AdvanceCurrentPosition(3);
1446
  m.PushBacktrack(&backtrack);
1447
  m.Succeed();
1448 1449
  m.Bind(&backtrack);
  m.ClearRegisters(2, 3);
1450
  m.Backtrack();
1451
  m.Bind(&fail);
1452 1453 1454
  m.PopRegister(0);
  m.Fail();

1455
  Isolate* isolate = CcTest::i_isolate();
1456 1457
  Factory* factory = isolate->factory();
  HandleScope scope(isolate);
1458

1459
  Handle<String> source = factory->NewStringFromStaticChars("^f(o)o");
1460 1461 1462 1463
  Handle<ByteArray> array = Handle<ByteArray>::cast(m.GetCode(source));
  int captures[5];

  const uc16 str1[] = {'f', 'o', 'o', 'b', 'a', 'r'};
1464 1465
  Handle<String> f1_16 = factory->NewStringFromTwoByte(
      Vector<const uc16>(str1, 6)).ToHandleChecked();
1466

1467
  CHECK(IrregexpInterpreter::Match(isolate, array, f1_16, captures, 0));
1468 1469 1470 1471 1472 1473 1474
  CHECK_EQ(0, captures[0]);
  CHECK_EQ(3, captures[1]);
  CHECK_EQ(1, captures[2]);
  CHECK_EQ(2, captures[3]);
  CHECK_EQ(84, captures[4]);

  const uc16 str2[] = {'b', 'a', 'r', 'f', 'o', 'o'};
1475 1476
  Handle<String> f2_16 = factory->NewStringFromTwoByte(
      Vector<const uc16>(str2, 6)).ToHandleChecked();
1477

1478
  CHECK(!IrregexpInterpreter::Match(isolate, array, f2_16, captures, 0));
1479 1480 1481
  CHECK_EQ(42, captures[0]);
}

1482
#endif  // V8_INTERPRETED_REGEXP
1483 1484


1485 1486 1487 1488
TEST(AddInverseToTable) {
  static const int kLimit = 1000;
  static const int kRangeCount = 16;
  for (int t = 0; t < 10; t++) {
1489
    Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1490
    ZoneList<CharacterRange>* ranges =
1491
        new(&zone) ZoneList<CharacterRange>(kRangeCount, &zone);
1492 1493 1494 1495
    for (int i = 0; i < kRangeCount; i++) {
      int from = PseudoRandom(t + 87, i + 25) % kLimit;
      int to = from + (PseudoRandom(i + 87, t + 25) % (kLimit / 20));
      if (to > kLimit) to = kLimit;
1496
      ranges->Add(CharacterRange::Range(from, to), &zone);
1497
    }
1498 1499
    DispatchTable table(&zone);
    DispatchTableConstructor cons(&table, false, &zone);
1500 1501 1502 1503 1504 1505 1506 1507 1508 1509
    cons.set_choice_index(0);
    cons.AddInverse(ranges);
    for (int i = 0; i < kLimit; i++) {
      bool is_on = false;
      for (int j = 0; !is_on && j < kRangeCount; j++)
        is_on = ranges->at(j).Contains(i);
      OutSet* set = table.Get(i);
      CHECK_EQ(is_on, set->Get(0) == false);
    }
  }
1510
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1511
  ZoneList<CharacterRange>* ranges =
1512
      new(&zone) ZoneList<CharacterRange>(1, &zone);
1513
  ranges->Add(CharacterRange::Range(0xFFF0, 0xFFFE), &zone);
1514 1515
  DispatchTable table(&zone);
  DispatchTableConstructor cons(&table, false, &zone);
1516 1517 1518 1519 1520 1521 1522 1523 1524
  cons.set_choice_index(0);
  cons.AddInverse(ranges);
  CHECK(!table.Get(0xFFFE)->Get(0));
  CHECK(table.Get(0xFFFF)->Get(0));
}


static uc32 canonicalize(uc32 c) {
  unibrow::uchar canon[unibrow::Ecma262Canonicalize::kMaxWidth];
1525
  int count = unibrow::Ecma262Canonicalize::Convert(c, '\0', canon, nullptr);
1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536
  if (count == 0) {
    return c;
  } else {
    CHECK_EQ(1, count);
    return canon[0];
  }
}


TEST(LatinCanonicalize) {
  unibrow::Mapping<unibrow::Ecma262UnCanonicalize> un_canonicalize;
1537 1538
  for (unibrow::uchar lower = 'a'; lower <= 'z'; lower++) {
    unibrow::uchar upper = lower + ('A' - 'a');
1539 1540 1541 1542 1543 1544 1545 1546 1547
    CHECK_EQ(canonicalize(lower), canonicalize(upper));
    unibrow::uchar uncanon[unibrow::Ecma262UnCanonicalize::kMaxWidth];
    int length = un_canonicalize.get(lower, '\0', uncanon);
    CHECK_EQ(2, length);
    CHECK_EQ(upper, uncanon[0]);
    CHECK_EQ(lower, uncanon[1]);
  }
  for (uc32 c = 128; c < (1 << 21); c++)
    CHECK_GE(canonicalize(c), 128);
1548
#ifndef V8_INTL_SUPPORT
1549
  unibrow::Mapping<unibrow::ToUppercase> to_upper;
1550 1551
  // Canonicalization is only defined for the Basic Multilingual Plane.
  for (uc32 c = 0; c < (1 << 16); c++) {
1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562
    unibrow::uchar upper[unibrow::ToUppercase::kMaxWidth];
    int length = to_upper.get(c, '\0', upper);
    if (length == 0) {
      length = 1;
      upper[0] = c;
    }
    uc32 u = upper[0];
    if (length > 1 || (c >= 128 && u < 128))
      u = c;
    CHECK_EQ(u, canonicalize(c));
  }
1563
#endif
1564 1565 1566
}


1567
static uc32 CanonRangeEnd(uc32 c) {
1568
  unibrow::uchar canon[unibrow::CanonicalizationRange::kMaxWidth];
1569
  int count = unibrow::CanonicalizationRange::Convert(c, '\0', canon, nullptr);
1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583
  if (count == 0) {
    return c;
  } else {
    CHECK_EQ(1, count);
    return canon[0];
  }
}


TEST(RangeCanonicalization) {
  // Check that we arrive at the same result when using the basic
  // range canonicalization primitives as when using immediate
  // canonicalization.
  unibrow::Mapping<unibrow::Ecma262UnCanonicalize> un_canonicalize;
1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599
  int block_start = 0;
  while (block_start <= 0xFFFF) {
    uc32 block_end = CanonRangeEnd(block_start);
    unsigned block_length = block_end - block_start + 1;
    if (block_length > 1) {
      unibrow::uchar first[unibrow::Ecma262UnCanonicalize::kMaxWidth];
      int first_length = un_canonicalize.get(block_start, '\0', first);
      for (unsigned i = 1; i < block_length; i++) {
        unibrow::uchar succ[unibrow::Ecma262UnCanonicalize::kMaxWidth];
        int succ_length = un_canonicalize.get(block_start + i, '\0', succ);
        CHECK_EQ(first_length, succ_length);
        for (int j = 0; j < succ_length; j++) {
          int calc = first[j] + i;
          int found = succ[j];
          CHECK_EQ(calc, found);
        }
1600 1601
      }
    }
1602
    block_start = block_start + block_length;
1603 1604 1605 1606
  }
}


1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622
TEST(UncanonicalizeEquivalence) {
  unibrow::Mapping<unibrow::Ecma262UnCanonicalize> un_canonicalize;
  unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
  for (int i = 0; i < (1 << 16); i++) {
    int length = un_canonicalize.get(i, '\0', chars);
    for (int j = 0; j < length; j++) {
      unibrow::uchar chars2[unibrow::Ecma262UnCanonicalize::kMaxWidth];
      int length2 = un_canonicalize.get(chars[j], '\0', chars2);
      CHECK_EQ(length, length2);
      for (int k = 0; k < length; k++)
        CHECK_EQ(static_cast<int>(chars[k]), static_cast<int>(chars2[k]));
    }
  }
}


1623
static void TestRangeCaseIndependence(Isolate* isolate, CharacterRange input,
1624
                                      Vector<CharacterRange> expected) {
1625
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1626
  int count = expected.length();
1627
  ZoneList<CharacterRange>* list =
1628
      new(&zone) ZoneList<CharacterRange>(count, &zone);
1629 1630 1631
  list->Add(input, &zone);
  CharacterRange::AddCaseEquivalents(isolate, &zone, list, false);
  list->Remove(0);  // Remove the input before checking results.
1632 1633 1634 1635 1636 1637 1638 1639
  CHECK_EQ(count, list->length());
  for (int i = 0; i < list->length(); i++) {
    CHECK_EQ(expected[i].from(), list->at(i).from());
    CHECK_EQ(expected[i].to(), list->at(i).to());
  }
}


1640 1641
static void TestSimpleRangeCaseIndependence(Isolate* isolate,
                                            CharacterRange input,
1642 1643 1644
                                            CharacterRange expected) {
  EmbeddedVector<CharacterRange, 1> vector;
  vector[0] = expected;
1645
  TestRangeCaseIndependence(isolate, input, vector);
1646 1647 1648 1649
}


TEST(CharacterRangeCaseIndependence) {
1650 1651
  Isolate* isolate = CcTest::i_isolate();
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Singleton('a'),
1652
                                  CharacterRange::Singleton('A'));
1653
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Singleton('z'),
1654
                                  CharacterRange::Singleton('Z'));
1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('a', 'z'),
                                  CharacterRange::Range('A', 'Z'));
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('c', 'f'),
                                  CharacterRange::Range('C', 'F'));
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('a', 'b'),
                                  CharacterRange::Range('A', 'B'));
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('y', 'z'),
                                  CharacterRange::Range('Y', 'Z'));
  TestSimpleRangeCaseIndependence(isolate,
                                  CharacterRange::Range('a' - 1, 'z' + 1),
                                  CharacterRange::Range('A', 'Z'));
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('A', 'Z'),
                                  CharacterRange::Range('a', 'z'));
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('C', 'F'),
                                  CharacterRange::Range('c', 'f'));
  TestSimpleRangeCaseIndependence(isolate,
                                  CharacterRange::Range('A' - 1, 'Z' + 1),
                                  CharacterRange::Range('a', 'z'));
1673 1674 1675
  // Here we need to add [l-z] to complete the case independence of
  // [A-Za-z] but we expect [a-z] to be added since we always add a
  // whole block at a time.
1676 1677
  TestSimpleRangeCaseIndependence(isolate, CharacterRange::Range('A', 'k'),
                                  CharacterRange::Range('a', 'z'));
1678 1679 1680
}


1681
static bool InClass(uc32 c, ZoneList<CharacterRange>* ranges) {
1682
  if (ranges == nullptr) return false;
1683 1684 1685 1686 1687 1688 1689 1690 1691
  for (int i = 0; i < ranges->length(); i++) {
    CharacterRange range = ranges->at(i);
    if (range.from() <= c && c <= range.to())
      return true;
  }
  return false;
}


1692
TEST(UnicodeRangeSplitter) {
1693
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1694
  ZoneList<CharacterRange>* base =
1695 1696
      new(&zone) ZoneList<CharacterRange>(1, &zone);
  base->Add(CharacterRange::Everything(), &zone);
1697 1698
  UnicodeRangeSplitter splitter(&zone, base);
  // BMP
1699
  for (uc32 c = 0; c < 0xD800; c++) {
1700 1701 1702 1703 1704 1705
    CHECK(InClass(c, splitter.bmp()));
    CHECK(!InClass(c, splitter.lead_surrogates()));
    CHECK(!InClass(c, splitter.trail_surrogates()));
    CHECK(!InClass(c, splitter.non_bmp()));
  }
  // Lead surrogates
1706
  for (uc32 c = 0xD800; c < 0xDBFF; c++) {
1707 1708 1709 1710 1711 1712
    CHECK(!InClass(c, splitter.bmp()));
    CHECK(InClass(c, splitter.lead_surrogates()));
    CHECK(!InClass(c, splitter.trail_surrogates()));
    CHECK(!InClass(c, splitter.non_bmp()));
  }
  // Trail surrogates
1713
  for (uc32 c = 0xDC00; c < 0xDFFF; c++) {
1714 1715 1716 1717 1718 1719
    CHECK(!InClass(c, splitter.bmp()));
    CHECK(!InClass(c, splitter.lead_surrogates()));
    CHECK(InClass(c, splitter.trail_surrogates()));
    CHECK(!InClass(c, splitter.non_bmp()));
  }
  // BMP
1720
  for (uc32 c = 0xE000; c < 0xFFFF; c++) {
1721 1722 1723 1724 1725 1726
    CHECK(InClass(c, splitter.bmp()));
    CHECK(!InClass(c, splitter.lead_surrogates()));
    CHECK(!InClass(c, splitter.trail_surrogates()));
    CHECK(!InClass(c, splitter.non_bmp()));
  }
  // Non-BMP
1727
  for (uc32 c = 0x10000; c < 0x10FFFF; c++) {
1728 1729 1730 1731
    CHECK(!InClass(c, splitter.bmp()));
    CHECK(!InClass(c, splitter.lead_surrogates()));
    CHECK(!InClass(c, splitter.trail_surrogates()));
    CHECK(InClass(c, splitter.non_bmp()));
1732 1733 1734 1735
  }
}


1736
TEST(CanonicalizeCharacterSets) {
1737
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1738
  ZoneList<CharacterRange>* list =
1739
      new(&zone) ZoneList<CharacterRange>(4, &zone);
1740 1741
  CharacterSet set(list);

1742 1743 1744
  list->Add(CharacterRange::Range(10, 20), &zone);
  list->Add(CharacterRange::Range(30, 40), &zone);
  list->Add(CharacterRange::Range(50, 60), &zone);
1745
  set.Canonicalize();
1746 1747 1748 1749 1750 1751 1752
  CHECK_EQ(3, list->length());
  CHECK_EQ(10, list->at(0).from());
  CHECK_EQ(20, list->at(0).to());
  CHECK_EQ(30, list->at(1).from());
  CHECK_EQ(40, list->at(1).to());
  CHECK_EQ(50, list->at(2).from());
  CHECK_EQ(60, list->at(2).to());
1753 1754

  list->Rewind(0);
1755 1756 1757
  list->Add(CharacterRange::Range(10, 20), &zone);
  list->Add(CharacterRange::Range(50, 60), &zone);
  list->Add(CharacterRange::Range(30, 40), &zone);
1758
  set.Canonicalize();
1759 1760 1761 1762 1763 1764 1765
  CHECK_EQ(3, list->length());
  CHECK_EQ(10, list->at(0).from());
  CHECK_EQ(20, list->at(0).to());
  CHECK_EQ(30, list->at(1).from());
  CHECK_EQ(40, list->at(1).to());
  CHECK_EQ(50, list->at(2).from());
  CHECK_EQ(60, list->at(2).to());
1766 1767

  list->Rewind(0);
1768 1769 1770 1771 1772
  list->Add(CharacterRange::Range(30, 40), &zone);
  list->Add(CharacterRange::Range(10, 20), &zone);
  list->Add(CharacterRange::Range(25, 25), &zone);
  list->Add(CharacterRange::Range(100, 100), &zone);
  list->Add(CharacterRange::Range(1, 1), &zone);
1773
  set.Canonicalize();
1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784
  CHECK_EQ(5, list->length());
  CHECK_EQ(1, list->at(0).from());
  CHECK_EQ(1, list->at(0).to());
  CHECK_EQ(10, list->at(1).from());
  CHECK_EQ(20, list->at(1).to());
  CHECK_EQ(25, list->at(2).from());
  CHECK_EQ(25, list->at(2).to());
  CHECK_EQ(30, list->at(3).from());
  CHECK_EQ(40, list->at(3).to());
  CHECK_EQ(100, list->at(4).from());
  CHECK_EQ(100, list->at(4).to());
1785 1786

  list->Rewind(0);
1787 1788 1789
  list->Add(CharacterRange::Range(10, 19), &zone);
  list->Add(CharacterRange::Range(21, 30), &zone);
  list->Add(CharacterRange::Range(20, 20), &zone);
1790
  set.Canonicalize();
1791 1792 1793
  CHECK_EQ(1, list->length());
  CHECK_EQ(10, list->at(0).from());
  CHECK_EQ(30, list->at(0).to());
1794 1795
}

1796 1797

TEST(CharacterRangeMerge) {
1798
  Zone zone(CcTest::i_isolate()->allocator(), ZONE_NAME);
1799 1800
  ZoneList<CharacterRange> l1(4, &zone);
  ZoneList<CharacterRange> l2(4, &zone);
1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814
  // Create all combinations of intersections of ranges, both singletons and
  // longer.

  int offset = 0;

  // The five kinds of singleton intersections:
  //     X
  //   Y      - outside before
  //    Y     - outside touching start
  //     Y    - overlap
  //      Y   - outside touching end
  //       Y  - outside after

  for (int i = 0; i < 5; i++) {
1815 1816
    l1.Add(CharacterRange::Singleton(offset + 2), &zone);
    l2.Add(CharacterRange::Singleton(offset + i), &zone);
1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830
    offset += 6;
  }

  // The seven kinds of singleton/non-singleton intersections:
  //    XXX
  //  Y        - outside before
  //   Y       - outside touching start
  //    Y      - inside touching start
  //     Y     - entirely inside
  //      Y    - inside touching end
  //       Y   - outside touching end
  //        Y  - disjoint after

  for (int i = 0; i < 7; i++) {
1831 1832
    l1.Add(CharacterRange::Range(offset + 2, offset + 4), &zone);
    l2.Add(CharacterRange::Singleton(offset + i), &zone);
1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851
    offset += 8;
  }

  // The eleven kinds of non-singleton intersections:
  //
  //       XXXXXXXX
  // YYYY                  - outside before.
  //   YYYY                - outside touching start.
  //     YYYY              - overlapping start
  //       YYYY            - inside touching start
  //         YYYY          - entirely inside
  //           YYYY        - inside touching end
  //             YYYY      - overlapping end
  //               YYYY    - outside touching end
  //                 YYYY  - outside after
  //       YYYYYYYY        - identical
  //     YYYYYYYYYYYY      - containing entirely.

  for (int i = 0; i < 9; i++) {
1852 1853
    l1.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);  // Length 8.
    l2.Add(CharacterRange::Range(offset + 2 * i, offset + 2 * i + 3), &zone);
1854 1855
    offset += 22;
  }
1856 1857
  l1.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);
  l2.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);
1858
  offset += 22;
1859 1860
  l1.Add(CharacterRange::Range(offset + 6, offset + 15), &zone);
  l2.Add(CharacterRange::Range(offset + 4, offset + 17), &zone);
1861 1862 1863 1864 1865 1866
  offset += 22;

  // Different kinds of multi-range overlap:
  // XXXXXXXXXXXXXXXXXXXXXX         XXXXXXXXXXXXXXXXXXXXXX
  //   YYYY  Y  YYYY  Y  YYYY  Y  YYYY  Y  YYYY  Y  YYYY  Y

1867 1868
  l1.Add(CharacterRange::Range(offset, offset + 21), &zone);
  l1.Add(CharacterRange::Range(offset + 31, offset + 52), &zone);
1869
  for (int i = 0; i < 6; i++) {
1870 1871
    l2.Add(CharacterRange::Range(offset + 2, offset + 5), &zone);
    l2.Add(CharacterRange::Singleton(offset + 8), &zone);
1872 1873 1874
    offset += 9;
  }

1875 1876
  CHECK(CharacterRange::IsCanonical(&l1));
  CHECK(CharacterRange::IsCanonical(&l2));
1877

1878 1879 1880
  ZoneList<CharacterRange> first_only(4, &zone);
  ZoneList<CharacterRange> second_only(4, &zone);
  ZoneList<CharacterRange> both(4, &zone);
1881
}
1882 1883


1884
TEST(Graph) {
1885
  Execute("\\b\\w+\\b", false, true, true);
1886
}
1887 1888 1889 1890


namespace {

1891
int* global_use_counts = nullptr;
1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940

void MockUseCounterCallback(v8::Isolate* isolate,
                            v8::Isolate::UseCounterFeature feature) {
  ++global_use_counts[feature];
}
}


// Test that ES2015 RegExp compatibility fixes are in place, that they
// are not overly broad, and the appropriate UseCounters are incremented
TEST(UseCountRegExp) {
  v8::Isolate* isolate = CcTest::isolate();
  v8::HandleScope scope(isolate);
  LocalContext env;
  int use_counts[v8::Isolate::kUseCounterFeatureCount] = {};
  global_use_counts = use_counts;
  CcTest::isolate()->SetUseCounterCallback(MockUseCounterCallback);

  // Compat fix: RegExp.prototype.sticky == undefined; UseCounter tracks it
  v8::Local<v8::Value> resultSticky = CompileRun("RegExp.prototype.sticky");
  CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
  CHECK_EQ(0, use_counts[v8::Isolate::kRegExpPrototypeToString]);
  CHECK(resultSticky->IsUndefined());

  // re.sticky has approriate value and doesn't touch UseCounter
  v8::Local<v8::Value> resultReSticky = CompileRun("/a/.sticky");
  CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
  CHECK_EQ(0, use_counts[v8::Isolate::kRegExpPrototypeToString]);
  CHECK(resultReSticky->IsFalse());

  // When the getter is caleld on another object, throw an exception
  // and don't increment the UseCounter
  v8::Local<v8::Value> resultStickyError = CompileRun(
      "var exception;"
      "try { "
      "  Object.getOwnPropertyDescriptor(RegExp.prototype, 'sticky')"
      "      .get.call(null);"
      "} catch (e) {"
      "  exception = e;"
      "}"
      "exception");
  CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
  CHECK_EQ(0, use_counts[v8::Isolate::kRegExpPrototypeToString]);
  CHECK(resultStickyError->IsObject());

  // RegExp.prototype.toString() returns '/(?:)/' as a compatibility fix;
  // a UseCounter is incremented to track it.
  v8::Local<v8::Value> resultToString =
      CompileRun("RegExp.prototype.toString().length");
1941
  CHECK_EQ(2, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
1942 1943 1944 1945 1946 1947 1948
  CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeToString]);
  CHECK(resultToString->IsInt32());
  CHECK_EQ(6,
           resultToString->Int32Value(isolate->GetCurrentContext()).FromJust());

  // .toString() works on normal RegExps
  v8::Local<v8::Value> resultReToString = CompileRun("/a/.toString().length");
1949
  CHECK_EQ(2, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960
  CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeToString]);
  CHECK(resultReToString->IsInt32());
  CHECK_EQ(
      3, resultReToString->Int32Value(isolate->GetCurrentContext()).FromJust());

  // .toString() throws on non-RegExps that aren't RegExp.prototype
  v8::Local<v8::Value> resultToStringError = CompileRun(
      "var exception;"
      "try { RegExp.prototype.toString.call(null) }"
      "catch (e) { exception = e; }"
      "exception");
1961
  CHECK_EQ(2, use_counts[v8::Isolate::kRegExpPrototypeStickyGetter]);
1962 1963 1964
  CHECK_EQ(1, use_counts[v8::Isolate::kRegExpPrototypeToString]);
  CHECK(resultToStringError->IsObject());
}
1965 1966 1967 1968 1969 1970

class UncachedExternalString
    : public v8::String::ExternalOneByteStringResource {
 public:
  const char* data() const override { return "abcdefghijklmnopqrstuvwxyz"; }
  size_t length() const override { return 26; }
1971
  bool IsCacheable() const override { return false; }
1972 1973 1974 1975 1976 1977 1978 1979 1980
};

TEST(UncachedExternalString) {
  v8::Isolate* isolate = CcTest::isolate();
  v8::HandleScope scope(isolate);
  LocalContext env;
  v8::Local<v8::String> external =
      v8::String::NewExternalOneByte(isolate, new UncachedExternalString())
          .ToLocalChecked();
1981 1982 1983
  CHECK(v8::Utils::OpenHandle(*external)->map() ==
        ReadOnlyRoots(CcTest::i_isolate())
            .uncached_external_one_byte_string_map());
1984 1985 1986 1987 1988
  v8::Local<v8::Object> global = env->Global();
  global->Set(env.local(), v8_str("external"), external).FromJust();
  CompileRun("var re = /y(.)/; re.test('ab');");
  ExpectString("external.substring(1).match(re)[1]", "z");
}
1989

1990
}  // namespace test_regexp
1991 1992
}  // namespace internal
}  // namespace v8