--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/re2b_test.scala	Wed Dec 21 03:06:18 2016 +0000
@@ -0,0 +1,50 @@
+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(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
+}
+
+
+lazy val f = Future {
+  assert(size(iterT(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068) 
+  assert(size(iterT(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8) 
+}
+
+Await.result(f, 120 second)