Experimental: Fixed bug in RegExp Parser. Added feature counting in parser.

regexp2000/test/cctest/test-regexp.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 53 matching lines @@
   const char* input_;
   const char* compile_error_;
 };
 
 
 static SmartPointer<char> Parse(const char* input) {
   v8::HandleScope scope;
   unibrow::Utf8InputBuffer<> buffer(input, strlen(input));
   ZoneScope zone_scope(DELETE_ON_EXIT);
   Handle<String> error;
-  RegExpTree* node = v8::internal::ParseRegExp(&buffer, &error);
+  RegExpTree* node = v8::internal::ParseRegExp(&buffer, &error, NULL);
   CHECK(node != NULL);
   CHECK(error.is_null());
   SmartPointer<char> output = node->ToString();
   return output;
 }
 
+static bool ParseEscapes(const char* input) {
+  v8::HandleScope scope;
+  unibrow::Utf8InputBuffer<> buffer(input, strlen(input));
+  ZoneScope zone_scope(DELETE_ON_EXIT);
+  Handle<String> error;
+  bool has_escapes;
+  RegExpTree* node = v8::internal::ParseRegExp(&buffer, &error, &has_escapes);
+  CHECK(node != NULL);
+  CHECK(error.is_null());
+  return has_escapes;
+}
+
 
 #define CHECK_PARSE_EQ(input, expected) CHECK_EQ(expected, *Parse(input))
-
+#define CHECK_ESCAPES(input, has_escapes) CHECK_EQ(has_escapes, \
+                                                   ParseEscapes(input));
 
 TEST(Parser) {
   V8::Initialize(NULL);
   CHECK_PARSE_EQ("abc", "'abc'");
   CHECK_PARSE_EQ("", "%");
   CHECK_PARSE_EQ("abc|def", "(| 'abc' 'def')");
   CHECK_PARSE_EQ("abc|def|ghi", "(| 'abc' 'def' 'ghi')");
   CHECK_PARSE_EQ("^xxx$", "(: @^i 'xxx' @$i)");
   CHECK_PARSE_EQ("ab\\b\\d\\bcd", "(: 'ab' @b [0-9] @b 'cd')");
   CHECK_PARSE_EQ("\\w|\\d", "(| [0-9 A-Z _ a-z] [0-9])");
   CHECK_PARSE_EQ("a*", "(# 0 - g 'a')");
   CHECK_PARSE_EQ("a*?", "(# 0 - n 'a')");
-  CHECK_PARSE_EQ("abc+", "(# 1 - g 'abc')");
-  CHECK_PARSE_EQ("abc+?", "(# 1 - n 'abc')");
-  CHECK_PARSE_EQ("xyz?", "(# 0 1 g 'xyz')");
-  CHECK_PARSE_EQ("xyz??", "(# 0 1 n 'xyz')");
-  CHECK_PARSE_EQ("xyz{0,1}", "(# 0 1 g 'xyz')");
-  CHECK_PARSE_EQ("xyz{0,1}?", "(# 0 1 n 'xyz')");
-  CHECK_PARSE_EQ("xyz{93}", "(# 93 93 g 'xyz')");
-  CHECK_PARSE_EQ("xyz{93}?", "(# 93 93 n 'xyz')");
-  CHECK_PARSE_EQ("xyz{1,32}", "(# 1 32 g 'xyz')");
-  CHECK_PARSE_EQ("xyz{1,32}?", "(# 1 32 n 'xyz')");
-  CHECK_PARSE_EQ("xyz{1,}", "(# 1 - g 'xyz')");
-  CHECK_PARSE_EQ("xyz{1,}?", "(# 1 - n 'xyz')");
+  CHECK_PARSE_EQ("abc+", "(: 'ab' (# 1 - g 'c'))");
+  CHECK_PARSE_EQ("abc+?", "(: 'ab' (# 1 - n 'c'))");
+  CHECK_PARSE_EQ("xyz?", "(: 'xy' (# 0 1 g 'z'))");
+  CHECK_PARSE_EQ("xyz??", "(: 'xy' (# 0 1 n 'z'))");
+  CHECK_PARSE_EQ("xyz{0,1}", "(: 'xy' (# 0 1 g 'z'))");
+  CHECK_PARSE_EQ("xyz{0,1}?", "(: 'xy' (# 0 1 n 'z'))");
+  CHECK_PARSE_EQ("xyz{93}", "(: 'xy' (# 93 93 g 'z'))");
+  CHECK_PARSE_EQ("xyz{93}?", "(: 'xy' (# 93 93 n 'z'))");
+  CHECK_PARSE_EQ("xyz{1,32}", "(: 'xy' (# 1 32 g 'z'))");
+  CHECK_PARSE_EQ("xyz{1,32}?", "(: 'xy' (# 1 32 n 'z'))");
+  CHECK_PARSE_EQ("xyz{1,}", "(: 'xy' (# 1 - g 'z'))");
+  CHECK_PARSE_EQ("xyz{1,}?", "(: 'xy' (# 1 - n 'z'))");
   CHECK_PARSE_EQ("a\\fb\\nc\\rd\\te\\vf", "'a\fb\nc\rd\te\vf'");
   CHECK_PARSE_EQ("a\\nb\\bc", "(: 'a\nb' @b 'c')");
   CHECK_PARSE_EQ("(?:foo)", "'foo'");
   CHECK_PARSE_EQ("(?: foo )", "' foo '");
   CHECK_PARSE_EQ("(foo|bar|baz)", "(^ (| 'foo' 'bar' 'baz'))");
   CHECK_PARSE_EQ("foo|(bar|baz)|quux", "(| 'foo' (^ (| 'bar' 'baz')) 'quux')");
   CHECK_PARSE_EQ("foo(?=bar)baz", "(: 'foo' (-> + 'bar') 'baz')");
   CHECK_PARSE_EQ("foo(?!bar)baz", "(: 'foo' (-> - 'bar') 'baz')");
   CHECK_PARSE_EQ("()", "(^ %)");
   CHECK_PARSE_EQ("(?=)", "(-> + %)");
@@ skipping 38 matching lines @@
   CHECK_PARSE_EQ("(x)(x)(x)\\3*", "(: (^ 'x') (^ 'x') (^ 'x')"
                                " (# 0 - g (<- 3)))");
   CHECK_PARSE_EQ("(x)(x)(x)\\4*", "(: (^ 'x') (^ 'x') (^ 'x')"
                                " (# 0 - g '\x04'))");
   CHECK_PARSE_EQ("(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)\\10",
               "(: (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x')"
               " (^ 'x') (^ 'x') (^ 'x') (^ 'x') (<- 10))");
   CHECK_PARSE_EQ("(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)\\11",
               "(: (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x') (^ 'x')"
               " (^ 'x') (^ 'x') (^ 'x') (^ 'x') '\x09')");
+  CHECK_PARSE_EQ("(a)\\1", "(: (^ 'a') (<- 1))");
+  CHECK_PARSE_EQ("(a\\1)", "(^ (: 'a' (<- 1)))");
+  CHECK_PARSE_EQ("(\\1a)", "(^ (: (<- 1) 'a'))");
+  CHECK_PARSE_EQ("\\1(a)", "(: '\x01' (^ 'a'))");
   CHECK_PARSE_EQ("[\\0]", "[\0]");
   CHECK_PARSE_EQ("[\\11]", "[\t]");
   CHECK_PARSE_EQ("[\\11a]", "[\t a]");
   CHECK_PARSE_EQ("[\\011]", "[\t]");
   CHECK_PARSE_EQ("[\\00011]", "[\000 1 1]");
   CHECK_PARSE_EQ("[\\118]", "[\t 8]");
   CHECK_PARSE_EQ("[\\111]", "[I]");
   CHECK_PARSE_EQ("[\\1111]", "[I 1]");
   CHECK_PARSE_EQ("\\x34", "'\x34'");
+  CHECK_PARSE_EQ("\\x60", "'\x60'");
   CHECK_PARSE_EQ("\\x3z", "'x3z'");
   CHECK_PARSE_EQ("\\u0034", "'\x34'");
   CHECK_PARSE_EQ("\\u003z", "'u003z'");
+
+  CHECK_ESCAPES("a", false);
+  CHECK_ESCAPES("a|b", false);
+  CHECK_ESCAPES("a\\n", true);
+  CHECK_ESCAPES("^a", false);
+  CHECK_ESCAPES("a$", false);
+  CHECK_ESCAPES("a\\b!", false);
+  CHECK_ESCAPES("a\\Bb", false);
+  CHECK_ESCAPES("a*", false);
+  CHECK_ESCAPES("a*?", false);
+  CHECK_ESCAPES("a?", false);
+  CHECK_ESCAPES("a??", false);
+  CHECK_ESCAPES("a{0,1}?", false);
+  CHECK_ESCAPES("a{1,1}?", false);
+  CHECK_ESCAPES("a{1,2}?", false);
+  CHECK_ESCAPES("a+?", false);
+  CHECK_ESCAPES("(a)", false);
+  CHECK_ESCAPES("(a)\\1", false);
+  CHECK_ESCAPES("(\\1a)", false);
+  CHECK_ESCAPES("\\1(a)", true);
+  CHECK_ESCAPES("a\\s", false);
+  CHECK_ESCAPES("a\\S", false);
+  CHECK_ESCAPES("a\\d", false);
+  CHECK_ESCAPES("a\\D", false);
+  CHECK_ESCAPES("a\\w", false);
+  CHECK_ESCAPES("a\\W", false);
+  CHECK_ESCAPES("a.", false);
+  CHECK_ESCAPES("a\\q", true);
+  CHECK_ESCAPES("a[a]", false);
+  CHECK_ESCAPES("a[^a]", false);
+  CHECK_ESCAPES("a[a-z]", false);
+  CHECK_ESCAPES("a[\\q]", false);
+  CHECK_ESCAPES("a(?:b)", false);
+  CHECK_ESCAPES("a(?=b)", false);
+  CHECK_ESCAPES("a(?!b)", false);
+  CHECK_ESCAPES("\\x60", true);
+  CHECK_ESCAPES("\\u0060", true);
+  CHECK_ESCAPES("\\cA", true);
+  CHECK_ESCAPES("\\q", true);
+  CHECK_ESCAPES("\\1112", true);
+  CHECK_ESCAPES("\\0", true);
+  CHECK_ESCAPES("(a)\\1", false);
 }
 
 
 static void ExpectError(const char* input,
                         const char* expected) {
   v8::HandleScope scope;
   unibrow::Utf8InputBuffer<> buffer(input, strlen(input));
   ZoneScope zone_scope(DELETE_ON_EXIT);
   Handle<String> error;
-  RegExpTree* node = v8::internal::ParseRegExp(&buffer, &error);
+  RegExpTree* node = v8::internal::ParseRegExp(&buffer, &error, NULL);
   CHECK(node == NULL);
   CHECK(!error.is_null());
   SmartPointer<char> str = error->ToCString(ALLOW_NULLS);
   CHECK_EQ(expected, *str);
 }
 
 
 TEST(Errors) {
   V8::Initialize(NULL);
   const char* kEndBackslash = "\\ at end of pattern";
@@ skipping 88 matching lines @@
   TestCharacterClassEscapes('w', IsWord);
   TestCharacterClassEscapes('W', NotWord);
 }
 
 
 static void Execute(bool expected, const char* input, const char* str) {
   v8::HandleScope scope;
   unibrow::Utf8InputBuffer<> buffer(input, strlen(input));
   ZoneScope zone_scope(DELETE_ON_EXIT);
   Handle<String> error;
-  RegExpTree* tree = v8::internal::ParseRegExp(&buffer, &error);
+  RegExpTree* tree = v8::internal::ParseRegExp(&buffer, &error, NULL);
   CHECK(tree != NULL);
   CHECK(error.is_null());
   RegExpNode<const char>* node = RegExpEngine::Compile<const char>(tree);
   bool outcome = RegExpEngine::Execute(node, CStrVector(str));
   CHECK_EQ(outcome, expected);
 }
 
 
 TEST(Execution) {
   V8::Initialize(NULL);
   Execute(true, ".*?(?:a[bc]d|e[fg]h)", "xxxabbegh");
   Execute(true, ".*?(?:a[bc]d|e[fg]h)", "xxxabbefh");
   Execute(false, ".*?(?:a[bc]d|e[fg]h)", "xxxabbefd");
 }
 
 
 class TestConfig {
  public:
   typedef int Key;
   typedef int Value;
   static const int kNoKey;
   static const int kNoValue;
   static inline int Compare(int a, int b) {
-    if (a < b) return -1;
-    else if (a > b) return 1;
-    else return 0;
+    if (a < b)
+      return -1;
+    else if (a > b)
+      return 1;
+    else
+      return 0;
   }
 };
 
 
 const int TestConfig::kNoKey = 0;
 const int TestConfig::kNoValue = 0;
 
 
 static int PseudoRandom(int i, int j) {
   return ~(~((i * 781) ^ (j * 329)));
@@ skipping 51 matching lines @@
         }
       }
     }
   }
 }
 
 
 static int CompareChars(const void* ap, const void* bp) {
   uc16 a = *static_cast<const uc16*>(ap);
   uc16 b = *static_cast<const uc16*>(bp);
-  if (a < b) return -1;
-  else if (a > b) return 1;
-  else return 0;
+  if (a < b)
+    return -1;
+  else if (a > b)
+    return 1;
+  else
+    return 0;
 }
 
 
 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++) {
@@ skipping 16 matching lines @@
     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));
     }
   }
 }