From 087c00043731ddf2b3a47e918ed91a6df9152fdd Mon Sep 17 00:00:00 2001 From: adam Date: Sun, 25 Feb 2007 20:38:28 -0500 Subject: [PATCH] add two test cases for O(n^2) behavior darcs-hash:20070226013828-5007d-ddf33d72c547f5cf1ae830700627f6e0ab1f56c8.gz --- tests/regression.tc | 39 +++++++++++++++++++++++++++++++-------- 1 file changed, 31 insertions(+), 8 deletions(-) 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" +} -- 1.7.10.4