From: adam <adam@megacz.com>
Date: Mon, 26 Feb 2007 01:38:28 +0000 (-0500)
Subject: add two test cases for O(n^2) behavior
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=087c00043731ddf2b3a47e918ed91a6df9152fdd;hp=795b267302e8829c3131bbeb1b291d63e9094f4d

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
--- a/tests/regression.tc
+++ b/tests/regression.tc
@@ -341,14 +341,6 @@ testcase {
     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 {
@@ -370,3 +362,34 @@ testcase {
   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"
+}