Limit EatAtLeast recursion by a budget.

test/mjsunit/regress/regress-crbug-178790.js

-// Copyright 2012 the V8 project authors. All rights reserved.
+// Copyright 2013 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
 //       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.
 
-// See: http://code.google.com/p/v8/issues/detail?id=1878
+// Create a regexp in the form of a?a?...a? so that fully
+// traversing the entire graph would be prohibitively expensive.
+// This should not cause time out.
+var r1 = "";
+for (var i = 0; i < 1000; i++) {
+  r1 += "a?";
+}
+"test".match(RegExp(r1));

[erikcorry, 2013/03/01 09:15:53]

It would be nice with a version with a lot of alternatives.  Something like:

(a?|b?|c?|d?|e?|f?)(a?|b?|c?|d?|e?f)...

 
-// Flags: --allow-natives-syntax --expose_natives_as=natives
+// Create a regexp in the form of ((..(a)a..)a.
+// Compiling it causes EatsAtLeast to reach the maximum
+// recursion depth possible with a given budget.
+// This should not cause a stack overflow.
+var r2 = "a";
+for (var i = 0; i < 1000; i++) {
+  r2 = "(" + r2 + ")a";
+}
+"test".match(RegExp(r2));
 
-var a = Array();
-
-for (var i = 0; i < 1000; i++) {
-  var ai = natives.InternalArray(10000);
-  assertFalse(%HaveSameMap(ai, a));
-  assertTrue(%HasFastObjectElements(ai));
-}
-
-for (var i = 0; i < 1000; i++) {
-  var ai = new natives.InternalArray(10000);
-  assertFalse(%HaveSameMap(ai, a));
-  assertTrue(%HasFastObjectElements(ai));
-}