add two test cases for O(n^2) behavior

darcs-hash:20070226013828-5007d-ddf33d72c547f5cf1ae830700627f6e0ab1f56c8.gz

diff --git a/tests/regression.tc b/tests/regression.tc
index 863f8d8..f13accf 100644 (file)
--- a/tests/regression.tc
+++ b/tests/regression.tc
@@ -341,14 +341,6 @@ testcase {
     x   = [123]
 }
 
     x   = [123]
 }
 

-testcase {
-  input "aaaaaaaa";
-  output "";
-  s = As & AAs
-  As = () | As "a"
-  AAs = () | AAs "aa"
-}
-

 // make sure follow restrictions are honored
 // when a string matches the empty string
 testcase {
 // make sure follow restrictions are honored
 // when a string matches the empty string
 testcase {

@@ -370,3 +362,34 @@ testcase {
   B  = b:: "b"
   C  = c:: "c"
 }
   B  = b:: "b"
   C  = c:: "c"
 }

+
+testcase {
+  input "aaaaaaaaaaaaaaaaaaaa";
+  output "";
+  s = As & AAs
+  As = () | As "a"
+  AAs = () | AAs "aa"
+}
+
+// pathological O(n^2) behavior
+testcase {
+  input "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
+  output "x";
+          s = x:: ManyA!
+     ManyA =  ()
+            | x:: A ManyA
+          A = ()! ("a" & ManyAB)
+    ManyAB = ()
+            | "a" ManyAB
+            | "b" ManyAB
+
+}
+
+// another O(n^2) example, tickles different epsilon behaviors
+testcase {
+  input "aaaa";
+  output "x:{x:{x:{x}}}";
+  s = x:: s A! | ()
+  A = "a" & B
+  B = () | B "a"
+}