Port and integrate the irregexp engine from V8

tests/language/regex/capture-3_test.dart

Index: tests/language/regex/capture-3_test.dart
diff --git a/tests/language/regex/capture-3_test.dart b/tests/language/regex/capture-3_test.dart
new file mode 100644
index 0000000000000000000000000000000000000000..fa58be63b5a2f9d4ebf3331f317171926a90b58c
--- /dev/null
+++ b/tests/language/regex/capture-3_test.dart
@@ -0,0 +1,94 @@
+// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import 'util.dart';
+import 'package:expect/expect.dart';
+
+void main() {
+  dynamic oneMatch(re) {
+    assertEquals("acd", "abcd".replaceAll(re, ""));
+  }
+
+  oneMatch(new RegExp(r"b"));
+  oneMatch(new RegExp(r"b"));
+
+  assertEquals("acdacd", "abcdabcd".replaceAll(new RegExp(r"b"), ""));
+
+  dynamic captureMatch(re) {
+    var match = firstMatch("abcd", re);
+    assertEquals("b", match.group(1));
+    assertEquals("c", match.group(2));
+  }
+
+  captureMatch(new RegExp(r"(b)(c)"));
+  captureMatch(new RegExp(r"(b)(c)"));
+
+  // A test that initially does a zero width match, but later does a non-zero
+  // width match.
+  var a = "foo bar baz".replaceAll(new RegExp(r"^|bar"), "");
+  assertEquals("foo  baz", a);
+
+  a = "foo bar baz".replaceAll(new RegExp(r"^|bar"), "*");
+  assertEquals("*foo * baz", a);
+
+  // We test FilterASCII using regexps that will backtrack forever.  Since
+  // a regexp with a non-ASCII character in it can never match an ASCII
+  // string we can test that the relevant node is removed by verifying that
+  // there is no hang.
+  dynamic NoHang(re) {
+    firstMatch("This is an ASCII string that could take forever", re);
+  }
+
+  NoHang(new RegExp(r"(((.*)*)*x)Ā"));  // Continuation after loop is filtered, so is loop.
+  NoHang(new RegExp(r"(((.*)*)*Ā)foo"));  // Body of loop filtered.
+  NoHang(new RegExp(r"Ā(((.*)*)*x)"));   // Everything after a filtered character is filtered.
+  NoHang(new RegExp(r"(((.*)*)*x)Ā"));   // Everything before a filtered character is filtered.
+  NoHang(new RegExp(r"[ćăĀ](((.*)*)*x)"));   // Everything after a filtered class is filtered.
+  NoHang(new RegExp(r"(((.*)*)*x)[ćăĀ]"));   // Everything before a filtered class is filtered.
+  NoHang(new RegExp(r"[^\x00-\xff](((.*)*)*x)"));   // After negated class.
+  NoHang(new RegExp(r"(((.*)*)*x)[^\x00-\xff]"));   // Before negated class.
+  NoHang(new RegExp(r"(?!(((.*)*)*x)Ā)foo"));  // Negative lookahead is filtered.
+  NoHang(new RegExp(r"(?!(((.*)*)*x))Ā"));  // Continuation branch of negative lookahead.
+  NoHang(new RegExp(r"(?=(((.*)*)*x)Ā)foo"));  // Positive lookahead is filtered.
+  NoHang(new RegExp(r"(?=(((.*)*)*x))Ā"));  // Continuation branch of positive lookahead.
+  NoHang(new RegExp(r"(?=Ā)(((.*)*)*x)"));  // Positive lookahead also prunes continuation.
+  NoHang(new RegExp(r"(æ|ø|Ā)(((.*)*)*x)"));  // All branches of alternation are filtered.
+  NoHang(new RegExp(r"(a|b|(((.*)*)*x))Ā"));  // 1 out of 3 branches pruned.
+  NoHang(new RegExp(r"(a|(((.*)*)*x)ă|(((.*)*)*x)Ā)"));  // 2 out of 3 branches pruned.
+
+  var s = "Don't prune based on a repetition of length 0";
+  assertEquals(null, firstMatch(s, new RegExp(r"å{1,1}prune")));
+  assertEquals("prune", (firstMatch(s, new RegExp(r"å{0,0}prune"))[0]));
+
+  // Some very deep regexps where FilterASCII gives up in order not to make the
+  // stack overflow.
+  var regex6 = new RegExp(r"a*\u0100*\w");
+  var input0 = "a";
+  regex6.firstMatch(input0);
+
+  var re = "\u0100*\\w";
+
+  for (var i = 0; i < 200; i++) re = "a*" + re;
+
+  var regex7 = new RegExp(re);
+  regex7.firstMatch(input0);
+
+  var regex8 = new RegExp(re, caseSensitive: false);
+  regex8.firstMatch(input0);
+
+  re = "[\u0100]*\\w";
+  for (var i = 0; i < 200; i++) re = "a*" + re;
+
+  var regex9 = new RegExp(re);
+  regex9.firstMatch(input0);
+
+  var regex10 = new RegExp(re, caseSensitive: false);
+  regex10.firstMatch(input0);
+
+  var regex11 = new RegExp(r"^(?:[^\u0000-\u0080]|[0-9a-z?,.!&\s#()])+$", caseSensitive: false);
+  regex11.firstMatch(input0);
+
+  var regex12 = new RegExp(r"u(\xf0{8}?\D*?|( ? !)$h??(|)*?(||)+?\6((?:\W\B|--\d-*-|)?$){0, }?|^Y( ? !1)\d+)+a");
+  regex12.firstMatch("");
+}