diff -r a057dc4457fc -r 87b9e3e2c1a7 marking/re2b_test.scala --- a/marking/re2b_test.scala Tue Oct 29 11:11:44 2019 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,56 +0,0 @@ -import scala.concurrent._ -import scala.concurrent.duration._ -import ExecutionContext.Implicits.global -import scala.language.postfixOps - -val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) - -def nullable_urban (r: Rexp) : Boolean = r match { - case ZERO => false - case ONE => true - case CHAR(_) => false - case ALT(r1, r2) => nullable_urban(r1) || nullable_urban(r2) - case SEQ(r1, r2) => nullable_urban(r1) && nullable_urban(r2) - case STAR(_) => true -} - -def der_urban (c: Char, r: Rexp) : Rexp = r match { - case ZERO => ZERO - case ONE => ZERO - case CHAR(d) => if (c == d) ONE else ZERO - case ALT(r1, r2) => ALT(der_urban(c, r1), der_urban(c, r2)) - case SEQ(r1, r2) => - if (nullable_urban(r1)) ALT(SEQ(der_urban(c, r1), r2), der_urban(c, r2)) - else SEQ(der_urban(c, r1), r2) - case STAR(r1) => SEQ(der_urban(c, r1), STAR(r1)) -} - -def simp_urban(r: Rexp) : Rexp = r match { - case ALT(r1, r2) => (simp_urban(r1), simp_urban(r2)) match { - case (ZERO, r2s) => r2s - case (r1s, ZERO) => r1s - case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) - } - case SEQ(r1, r2) => (simp_urban(r1), simp_urban(r2)) match { - case (ZERO, _) => ZERO - case (_, ZERO) => ZERO - case (ONE, r2s) => r2s - case (r1s, ONE) => r1s - case (r1s, r2s) => SEQ(r1s, r2s) - } - case r => r -} - -import scala.annotation.tailrec - -@tailrec -def iterT_urban[A](n: Int, f: A => A, x: A): A = - if (n == 0) x else iterT_urban(n - 1, f, f(x)) - - -lazy val f = Future { - assert(size(iterT_urban(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068) - assert(size(iterT_urban(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8) -} - -Await.result(f, 90 second)