1 // package zre 

     2 //Zre5: eliminated mems table

     3 

     4 

     5 

     6 import scala.collection.mutable.{Map => MMap}

     7 import scala.collection.mutable.{ArrayBuffer => MList}

     8 //import pprint._

     9 

    10 import scala.util.Try

    11 import pprint._

    12 

    13 

    14 abstract class Val

    15 case object Empty extends Val

    16 case class Chr(c: Char) extends Val

    17 case class Sequ(v1: Val, v2: Val) extends Val

    18 case class Left(v: Val) extends Val

    19 case class Right(v: Val) extends Val

    20 case class Stars(vs: List[Val]) extends Val

    21 case object DummyFilling extends Val

    22 

    23 

    24 // abstract class Rexp {

    25 //      def equals(other: Rexp) : Boolean = this.eq(other)

    26 // }

    27 abstract class Rexp

    28 case object ZERO extends Rexp                    // matches nothing

    29 case object ONE extends Rexp                     // matches an empty string

    30 case class CHAR(c: Char) extends Rexp            // matches a character c

    31 case class ALT(r1: Rexp, r2: Rexp) extends Rexp  // alternative

    32 case class AL1(r1: Rexp) extends Rexp

    33 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence

    34 case class STAR(r: Rexp) extends Rexp

    35 case object RTOP extends Rexp

    36 

    37 

    38 //Seq a b --> Seq Seqa Seqb

    39 //Seq a b --> Sequ chra chrb

    40 //ALT r1 r2 --> mALT

    41 //         AltC L   AltC R

    42 var cyclicPreventionList : Set[Int]= Set()

    43 abstract class Ctx(var starIters: Int = 0){

    44     //starIters = 0

    45 }

    46 case object RootC extends Ctx

    47 case class SeqC( mForMyself:  Mem, processedSibling: List[Val], unpSibling: List[Rexp]) extends Ctx 

    48 case class AltC( mForMyself:  Mem, wrapper: Val => Val) extends Ctx

    49 case class StarC(mForMyself:  Mem, vs: List[Val], inside: Rexp) extends Ctx

    50 

    51 case class Mem(var parents: MList[Ctx], var result : MList[(Int, Val)])

    52 

    53 //AltC(Mem(RootC::Nil, Map()))

    54 

    55 

    56 

    57 type Zipper = (Val, Mem)

    58 

    59 var mems : MMap[(Int, Rexp), Mem] = MMap()

    60         //start pos, original regex --> result entry

    61 

    62 

    63 var pos : Int = 0

    64 

    65 

    66 

    67 //input ..................

    68 //          ^       ^

    69 //          p       q

    70 //          r

    71 

    72 //parse r[p...q] --> v

    73 

    74 //(a+aa)*

    75 //aaa

    76 //[R(Sequ(a, a)), vs]

    77 //[L(a), L(a), vs]

    78 def check_before_down(c: Ctx, r: Rexp, starIters: Int = 0) : List[Zipper] = {

    79     c.starIters = starIters

    80     mems.get((pos, r)) match {

    81         case Some(m) => 

    82             // c match {

    83             //     case StarC(m, vs, inside) => vs.length

    84             // }

    85             val idx = m.parents.lastIndexWhere(c0 => c0.starIters < c.starIters)

    86             if(m.parents.size == 2){

    87                 println("third parent added")

    88                 println(simpleCtxDisplay(c))

    89                 println("the other parents")

    90                 m.parents.foreach(c00 => println(c00.starIters))

    91                 println(idx + 1)

    92                 println("c's star iters: "+ c.starIters)

    93                 println(s"the others' star iters: ${m.parents(0).starIters}")

    94             }

    95             m.parents.insert(idx + 1, c)

    96             //m.parents = m.parents:::List(c)

    97             m.result.find(endPos_value => endPos_value._1 == pos) match {

    98                 // case Some((i, v)) => 

    99                 //   original_up(v, c, starIters)

   100                 case None => 

   101                   List()

   102             }

   103         case None => 

   104             val m = Mem(MList(c), MList.empty[(Int, Val)])

   105             mems = mems + ((pos, r) -> m)

   106             original_down(r, m, starIters)

   107     }

   108     // val m = Mem(c::Nil, MList.empty[(Int, Val)])

   109     // original_down(r, m, d)

   110 }

   111 

   112 //mems  pstart r  --> m parents [(pend, vres), ...]

   113 //aaa

   114 //012

   115 //seq a a 

   116 //0 a~a --> m ... [(2, Sequ a a)]

   117         // c match {

   118         //     case StarC(mst, vst, rst) => print(s"StarC $vst\t")

   119         //     case SeqC(mse, pr, unp) => print(s"SeqC $unp\t")

   120         //     case AltC(mal, w) => print(s"AltC ${w(Empty)}\t")

   121         //     case RootC => print("Root")

   122         // }

   123 def reorderCtx(cs: List[Ctx]): List[Ctx] = {

   124     Nil

   125 }

   126 

   127 def mem_up(vres: Val, m: Mem, starIters : Int = 0) : List[Zipper] = {

   128     m.result += (pos -> vres)

   129     //m.parents = m.parents.reverse

   130           

   131     // if(m.parents.size > 1){//println()

   132     //     println()  

   133     //     println("each of the contexts")

   134     //     m.parents.reverse.foreach (c =>

   135     //         println(simpleCtxDisplay(c))

   136     //     )

   137     //     println("after distinctCtx")

   138     //     distinctCtx(m.parents.reverse).foreach(c =>

   139     //         println(simpleCtxDisplay(c))

   140     //     )

   141     //     //println(s"vs is $vss")

   142     

   143     // }

   144     //.distinctBy(zipBackToRegex(_))

   145     //TODO: too many arraybuffer->list conversions

   146     (m.parents).distinctBy(zipBackToRegex(_)).flatMap((c: Ctx) =>

   147         original_up(vres, c, starIters)

   148     ).toList

   149     // m.parents.reverse.flatMap((c: Ctx) =>

   150     //     original_up(vres, c, rec_depth)

   151     // )

   152     // original_up(vres, m.parents.last, rec_depth)

   153 }

   154 

   155 def original_down(r: Rexp, m: Mem, starIters: Int = 0) : List[Zipper] = (r, m) match {

   156     case (CHAR(b), m) => {

   157         if (input(pos) == b) {

   158             List((Chr(b), m)) 

   159         }

   160         else 

   161             Nil

   162     }

   163     case (ONE, m) => Nil//mem_up(Empty, m, starIters)

   164     case (SEQ(r1, r2), m) =>  

   165         // if(nullable(r1)){

   166         //     val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)])

   167         //     check_before_down(SeqC(mprime, Nil, List(r2)), r1, starIters) :::

   168         //     check_before_down(SeqC(mprime, mkeps(r1)::Nil, Nil), r2, starIters)

   169         // }

   170         // else

   171             check_before_down(SeqC(m, Nil, List(r2)), r1, starIters)

   172     case (ALT(r1, r2), m) => 

   173         check_before_down(AltC(m, Left(_)), r1, starIters) ::: 

   174         check_before_down(AltC(m, Right(_)), r2, starIters)

   175     case (STAR(r0), m) =>

   176         check_before_down(StarC(m, Nil, r0), r0, starIters) :::

   177         mem_up(Stars(Nil), m, starIters)

   178     case (_, _) => throw new Exception("original down unexpected r or m")

   179 }

   180 

   181 def original_up(v: Val, c: Ctx, starIters: Int = 0) : List[Zipper] = 

   182 {

   183 

   184 (v, c) match {

   185     case (v, SeqC(m, v1::Nil, Nil)) => 

   186         mem_up(Sequ(v1, v), m, starIters)

   187     case (v, SeqC(m, vs, u1::Nil)) => 

   188         check_before_down(SeqC(m, v::vs, Nil), u1, starIters)

   189     case (v, AltC(m, wrap)) => m.result.find(tup2 => tup2._1 == pos) match {

   190         case Some( (i, vPrime)  ) => 

   191             m.result += (i -> wrap(v))

   192             Nil

   193         case None => 

   194             mem_up(wrap(v), m, starIters)

   195     } //mem_up(AL1(v), par)

   196     //case (v, StarC(m, vs, r0)) => throw new Exception("why not hit starC")

   197 

   198     case (v, RootC) => 

   199         Nil

   200     case (v, StarC(m, vs, r0) ) => //mem_up(Stars(v::vs), m, starIters) //::: 

   201         check_before_down(StarC(m, v::vs, r0), r0, starIters + 1) :::

   202         mem_up(Stars((v::vs).reverse), m, starIters)

   203     case (_, _) => throw new Exception("hit unexpected context")

   204 }

   205 

   206 }

   207 

   208 

   209 def derive(p: Int, z: Zipper) : List[Zipper] = {

   210     pos = p

   211     //println(s"z's actual size is ${actualZipperSize(z::Nil)}")

   212     

   213     z match {

   214         case (v, m) => 

   215             

   216             mem_up(v, m)

   217         case _ => throw new Exception("error")

   218     }

   219 }

   220 //let e' = Seq([]) in 

   221 //

   222 def init_zipper(r: Rexp) : Zipper = {

   223     val m_top = Mem(MList(RootC), MList.empty[(Int, Val)])

   224     val c_top = SeqC(m_top, Nil, r::Nil)

   225     val m_r = Mem(MList(c_top), MList.empty[(Int, Val)])

   226     println(s"initial zipper is (Empty, $m_r)")

   227     (Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter

   228     // val dummyRexp = ONE

   229     // val dummyMem = Mem()

   230 

   231 }

   232 

   233 

   234 def plug_convert(v: Val, c: Ctx) : List[Val] = 

   235 {

   236 

   237 c match {

   238     case RootC => List(v)

   239     //TODO: non-binary Seq requires ps.rev

   240     case SeqC(m, ps::Nil, Nil) => 

   241         plug_mem(Sequ(ps, v), m)

   242 

   243     //TODO: un not nullable--partial values?

   244     case SeqC(m, Nil, un::Nil) => 

   245         if(nullable(un))

   246             plug_mem(Sequ(v, mkeps(un)), m)

   247         else

   248             Nil

   249 

   250     //TODO: when multiple results stored in m, which one to choose?

   251     case AltC(m, wrap) => 

   252         plug_mem(wrap(v), m)

   253     case StarC(m, vs, r0) => plug_mem(Stars((v::vs).reverse), m)

   254 }

   255 

   256 }

   257 

   258 

   259 var cnt = 0;

   260 def plug_mem(v: Val, m: Mem) : List[Val] = {

   261     m.result += (pos -> v)

   262     //TODO: eliminate arraybuffer->list conversion

   263     m.parents.flatMap({c =>

   264         plug_convert(v, c)

   265     }

   266     ).toList

   267 }

   268 

   269 def plug_all(zs: List[Zipper]) : List[Val] = {

   270     zs.flatMap(z => plug_mem(z._1, z._2))

   271 }

   272 

   273 

   274 def mkeps(r: Rexp) : Val = r match {

   275   case ONE => Empty

   276   case ALT(r1, r2) => 

   277     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))

   278   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))

   279   case _ => DummyFilling

   280 }

   281 

   282 def nullable(r: Rexp) : Boolean = r match {

   283   case ZERO => false

   284   case ONE => true

   285   case CHAR(_) => false

   286   case ALT(r1, r2) => nullable(r1) || nullable(r2)

   287   case SEQ(r1, r2) => nullable(r1) && nullable(r2)

   288   case _ => false

   289 }

   290 

   291 

   292 val tokList : List[Char] = "aab".toList

   293 var input : List[Char] = tokList

   294 

   295 

   296 

   297 

   298 

   299 

   300 

   301 def lexRecurse(zs: List[Zipper], index: Int) : List[Zipper] = {

   302     if(index <  input.length )

   303         lexRecurse(zs.flatMap(z => derive(index, z) ), index + 1)

   304     else 

   305         zs

   306 }

   307 

   308 def lex(r: Rexp, s: String) : List[Zipper] = {

   309     input = s.toList

   310     

   311     lexRecurse(init_zipper(r)::Nil,  0)

   312 }

   313 

   314 

   315 

   316 implicit def charlist2rexp(s: List[Char]): Rexp = s match {

   317     case Nil => ONE

   318     case c::Nil => CHAR(c)

   319     case c::cs => SEQ(CHAR(c), charlist2rexp(cs))

   320 }

   321 implicit def string2Rexp(s: String) : Rexp = charlist2rexp(s.toList)

   322 

   323 implicit def RexpOps(r: Rexp) = new {

   324     def | (s: Rexp) = ALT(r, s)

   325     def ~ (s: Rexp) = SEQ(r, s)

   326     def % = STAR(r)

   327 }

   328 

   329 implicit def stringOps(s: String) = new {

   330     def | (r: Rexp) = ALT(s, r)

   331     def | (r: String) = ALT(s, r)

   332     def ~ (r: Rexp) = SEQ(s, r)

   333     def ~ (r: String) = SEQ(s, r)

   334     def % = STAR(s)

   335 

   336 }

   337 

   338 //derive(0, init_zipper(re0))

   339 

   340 // println(re1s.length)

   341 // mems.foreach(a => println(a))

   342 // val re1sPlugged = plug_all(re1s)

   343 // re1sPlugged.foreach(zipper => {

   344 //                         println(zipper); 

   345 //                         println("delimit") 

   346 //                         })

   347                 

   348 // mems.clear()

   349 // println(mems)

   350 // println(re0)

   351 // val re2s = lex(re0, "aab")

   352 // val re2sPlugged = plug_all(re2s)

   353 // re2sPlugged.foreach(v => {

   354 //         val Sequ(Empty, vp) = v

   355 //         println(vp)

   356 //     }

   357 // )

   358 // val re0 = SEQ(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a'))), 

   359 // ALT(SEQ(CHAR('a'), CHAR('b')), SEQ(CHAR('b'), CHAR('c')) )

   360 // )

   361 

   362 // val (rgraph, re0root) = makeGraphFromObject(re0)

   363 // val asciir = GraphLayout.renderGraph(rgraph)

   364 // println("printing out re0")

   365 // println(asciir)

   366 // val re1s = lex(re0, "aabc")

   367  

   368 def actualZipperSize(zs: List[Zipper]) : Int = zs match {

   369     case Nil => 0

   370     case z::zs1 => countParents(z._2) + actualZipperSize(zs1)

   371 }

   372 

   373 def countParents(m: Mem) : Int = {

   374     m.parents.map(c => countGrandParents(c)).sum

   375 }

   376 

   377 def countGrandParents(c: Ctx) : Int = {

   378     c match {

   379         case RootC => 1

   380         case SeqC(m, pr, unp) => countParents(m)

   381         case AltC(m, w) => countParents(m)

   382         case StarC(m, _, _) => countParents(m)

   383     }

   384 }

   385 //(a+aa)* \a --> (1 + a)(a+aa)* --> (a+aa)* + (1+a)(a+aa)*

   386 

   387 //a(a+aa)* + 1(a+aa)* + (a+aa)*

   388 

   389 //a~(a + aa)* \a -> 1 ~ (a + aa)* 

   390 //va <-----> m --> SeqC(m1, pr, "a") --> AltC(m4, Right)--> StarC(m2, vs, "a" + "aa") --> SeqC(m) ---> Root

   391 //           ^

   392 //           ---> AltC(m4, Left) 

   393 def zipBackToRegex(c: Ctx, r: Rexp = ONE) : Rexp = {

   394     c match {

   395         case RootC => r

   396         case SeqC(m, pr, Nil) => zipBackToRegex(m.parents.head, r)

   397         case SeqC(m, pr, unp::Nil) => zipBackToRegex(m.parents.head, SEQ(r, unp))

   398         case AltC(m, w) => zipBackToRegex(m.parents.head, r)

   399         case StarC(m, vs, r0) => zipBackToRegex(m.parents.head, SEQ(r, STAR(r0)))

   400     }

   401 }

   402 

   403 def zipperSimp(z: Zipper) : Unit = z match {

   404     case (v, m) => //m.parents = m.parents.distinctBy(c => zipBackToRegex(c))

   405 }

   406 

   407 def distinctCtx(cs: List[Ctx]) : List[Ctx] = cs.distinctBy(c => zipBackToRegex(c))

   408 

   409 

   410 def simpleCtxDisplay(c: Ctx, indent : Int = 0) : String = c match {

   411     case SeqC(m, pr, unp) => "Sc[m:" ++ printMem(m, indent + 1) ++ 

   412         "pr:" ++ pr.map(v => shortValOutput(v)).mkString(", ") ++ " unp:" ++ unp.map(r2 => shortRexpOutput(r2)).mkString(", ") ++ "]"

   413     case AltC(m, w) =>

   414         w(Empty) match {

   415             case Left(_) => s"Ac(m:${printMem(m, indent + 1)}, Left(_))"

   416             case Right(_) => s"Ac(m:${printMem(m, indent + 1)}, Right(_))"

   417             case Empty => s"Ac(m:${printMem(m, indent + 1)}, id)"

   418         } 

   419     case StarC(m, vs, r0) => s"StarC[m:" ++ printMem(m, indent + 1) ++ 

   420         "vs:" ++ vs.map(v => shortValOutput(v)).mkString(", ") ++ " r0: " ++ shortRexpOutput(r0)

   421     case RootC => "Root"

   422     //case AL1(r) => s"(+${shortRexpOutput(r)})"

   423     //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"

   424     //case RTOP => "RTOP"

   425   }

   426 

   427 def printMem(m: Mem, indent: Int = 0) : String = {

   428    "M(par:" ++

   429    m.parents.map(c => simpleCtxDisplay(c, indent + 1)).mkString("(",",", ")")  ++

   430   ("， results:")  ++

   431   (for(iRexp <- m.result) 

   432     yield iRexp match {case (p: Int, v: Val) => s"$p->${shortValOutput(v)}"}

   433   ).mkString("(",",", ")")  ++ 

   434    ")" 

   435 }

   436 

   437 def shortRexpOutput(r: Rexp) : String = r match {

   438     case CHAR(c) => c.toString

   439     case ONE => "1"

   440     case ZERO => "0"

   441     case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"

   442     case ALT(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"

   443     case STAR(r) => "[" ++ shortRexpOutput(r) ++ "]*"

   444     //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"

   445     case RTOP => "RTOP"

   446   }

   447 

   448 def shortValOutput(v: Val) : String = v match {

   449     case Left(v) => "L(" ++ shortValOutput(v) ++ ")"

   450     case Right(v) => "R(" ++ shortValOutput(v) ++ ")"

   451     case Empty => "e"

   452     case Sequ(v1, v2) => "[" ++ shortValOutput(v1) ++ "~" ++ shortValOutput(v2) ++ "]"

   453     case Chr(a) => a.toString

   454     case Stars(vs) => "Stars" ++ vs.map(shortValOutput(_)).mkString("[", ",", "]")

   455     case _ => "???"

   456 }

   457 

   458 

   459 //def crystalizeZipper

   460 

   461 for(i <- 1 to 2) {

   462     mems.clear()

   463 println(s"there are $i number of a's")

   464 val re1 = ("a" | "aa" | "ab").%//(("a" | "b") ~ "c" | ("b" | "e") ~ "c" ) ~ "f"

   465 val re1Lexed = lex(re1, "a"*i)

   466 

   467 //drawZippers(re1Lexed)

   468 println("size of actual zipper (including memoized contexts")

   469 println(actualZipperSize(re1Lexed))

   470 //println(re1Lexed)

   471 //re1Lexed.foreach(zipperSimp(_))

   472 //println(actualZipperSize(re1S))

   473 val re1resPlugged = plug_all(re1Lexed)

   474 //println(actualZipperSize(re1Lexed))

   475 

   476 println("value extracted")

   477 re1resPlugged.foreach(v => {

   478         val Sequ(Empty, vp) = v

   479         println(vp)

   480 }

   481 )

   482 

   483   val mb = 1024*1024

   484 val runtime = Runtime.getRuntime

   485 println("ALL RESULTS IN MB")

   486 println("** Used Memory:  " + (runtime.totalMemory - runtime.freeMemory) / mb)

   487 println("** Free Memory:  " + runtime.freeMemory / mb)

   488 println("** Total Memory: " + runtime.totalMemory / mb)

   489 println("** Max Memory:   " + runtime.maxMemory / mb)

   490 

   491 }

   492 

   493 mems.clear()

   494 val re2 = SEQ(ONE, "a")

   495 val re2res = lex(re2, "a")

   496 //lex(1~a, "a") --> lexRecurse((1v, m  (SeqC(m (RootC, Nil), Nil, [1~a] ) )))

   497 

   498 

   499 println(re2res)

   500 

   501 val re2resPlugged = plug_all(re2res)

   502 re2resPlugged.foreach(v => {

   503         val Sequ(Empty, vp) = v

   504         println(vp)

   505 }

   506 )

   507 

   508 // println("remaining regex")

   509 // println(re1ss.flatMap(z => zipBackMem(z._2)))

   510 

   511 

   512 // val re1ssPlugged = plug_all(re1ss)

   513 // println("each of the values")

   514 // re1ssPlugged.foreach(v => {

   515 //         //val Sequ(Empty, vp) = v

   516 //         //println(vp)

   517 //         println(v)

   518 //     }

   519 // )

   520 // println(mems.size)

   521 //println(mems)

   522 //mems.map({case (ir, m) => if (ir._1 == 1 && ir._2 == CHAR('b')) println(printMem(m)) })

   523 // println("Mkeps + inj:")

   524 // println(

   525 //     mems.get((0, re1)) match {

   526 //         case Some(m) => printMem(m)

   527 //         case None => ""

   528 //     }

   529 //     )

   530 

   531 // println(re1sPlugged)

   532 //drawZippers(re1s, plugOrNot = false)

   533 // re1s.foreach{

   534 //   re1 => 

   535 //   {

   536 

   537 //     drawZippers(derive(1, re1), plugOrNot = true)

   538 

   539 //   }

   540 // }

   541 

   542