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 

    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   

    44 case object RootC extends Ctx

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

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

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

    48 

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

    50 

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

    52 

    53 

    54 

    55 type Zipper = (Val, Mem)

    56 

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

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

    59 

    60 

    61 var pos : Int = 0

    62 

    63 

    64 

    65 //input ..................

    66 //          ^       ^

    67 //          p       q

    68 //          r

    69 

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

    71 

    72 

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

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

    75         case Some(m) => 

    76             m.parents = c::Nil//c::m.parents

    77             m.result.find(tup2 => tup2._1 == pos) match {

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

    79                 //   original_up(v, c, d)

    80                 case None => 

    81                   List()

    82             }

    83         case None => 

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

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

    86             original_down(r, m, d)

    87     }

    88 }

    89 

    90 

    91 

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

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

    94     m.parents.flatMap((c: Ctx) =>

    95         original_up(vres, c, rec_depth)

    96     )

    97 }

    98 

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

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

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

   102             List((Chr(b), m)) 

   103         }

   104         else 

   105             Nil

   106     }

   107     case (ONE, m) => mem_up(Empty, m, d + 1)

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

   109           

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

   111          

   112         check_before_down(SeqC(mprime, Nil, List(r2)), r1, d)

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

   114          

   115         check_before_down(AltC(m, Left(_)), r1, d) ::: 

   116         check_before_down(AltC(m, Right(_)), r2, d)

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

   118          

   119         check_before_down(StarC(m, Nil, r0), r0, d)

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

   121 }

   122 

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

   124 {

   125 

   126 (v, c) match {

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

   128         mem_up(Sequ(v1, v), m, d + 1)

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

   130         check_before_down(SeqC(m, v::Nil, Nil), u1, d)

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

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

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

   134             Nil

   135         case None => 

   136             mem_up(wrap(v), m, d + 1)

   137     } //mem_up(AL1(r), par)

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

   139 

   140     case (v, RootC) => 

   141         Nil

   142     case (v, StarC(m, vs, r0) ) => mem_up(Stars(v::vs), m, d + 1) ::: 

   143         check_before_down(StarC(m, v::vs, r0), r0, d)

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

   145 }

   146 

   147 }

   148 

   149 

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

   151     pos = p

   152     z match {

   153         case (v, m) => mem_up(v, m)

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

   155     }

   156 }

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

   158 //

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

   160     val m_top = Mem(RootC::Nil, MList.empty[(Int, Val)])

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

   162     val m_r = Mem(c_top::Nil, MList.empty[(Int, Val)])

   163     println(s"initial zipper is (ZERO, $m_r)")

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

   165     // val dummyRexp = ONE

   166     // val dummyMem = Mem()

   167 

   168 }

   169 

   170 

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

   172 {

   173 

   174 c match {

   175     case RootC => List(v)

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

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

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

   179 

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

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

   182         if(nullable(un))

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

   184         else

   185             Nil

   186 

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

   188     case AltC(m, wrap) => 

   189         plug_mem(wrap(v), m)

   190     case StarC(m, vs, r0) => plug_mem(Stars(v::vs), m)

   191 }

   192 

   193 }

   194 

   195 

   196 var cnt = 0;

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

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

   199     m.parents.flatMap({c =>

   200         plug_convert(v, c)

   201     }

   202     )

   203 }

   204 

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

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

   207 }

   208 

   209 

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

   211   case ONE => Empty

   212   case ALT(r1, r2) => 

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

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

   215   case _ => DummyFilling

   216 }

   217 

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

   219   case ZERO => false

   220   case ONE => true

   221   case CHAR(_) => false

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

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

   224   case _ => false

   225 }

   226 

   227 

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

   229 var input : List[Char] = tokList

   230 

   231 

   232 

   233 

   234 

   235 

   236 

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

   238     if(index <  input.length )

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

   240     else 

   241         zs

   242 }

   243 

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

   245     input = s.toList

   246     

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

   248 }

   249 

   250 

   251 

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

   253     case Nil => ONE

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

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

   256 }

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

   258 

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

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

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

   262     def % = STAR(r)

   263 }

   264 

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

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

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

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

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

   270     def % = STAR(s)

   271 

   272 }

   273 

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

   275 

   276 // println(re1s.length)

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

   278 // val re1sPlugged = plug_all(re1s)

   279 // re1sPlugged.foreach(zipper => {

   280 //                         println(zipper); 

   281 //                         println("delimit") 

   282 //                         })

   283                 

   284 // mems.clear()

   285 // println(mems)

   286 // println(re0)

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

   288 // val re2sPlugged = plug_all(re2s)

   289 // re2sPlugged.foreach(v => {

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

   291 //         println(vp)

   292 //     }

   293 // )

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

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

   296 // )

   297 

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

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

   300 // println("printing out re0")

   301 // println(asciir)

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

   303 

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

   305     case Nil => 0

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

   307 }

   308 

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

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

   311 }

   312 

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

   314     c match {

   315         case RootC => 1

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

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

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

   319     }

   320 }

   321 

   322 def zipperSimp(zs: List[Zipper]) : List[Zipper] = {

   323     zs.distinctBy(z => zipBackMem(z._2))

   324 }

   325 

   326 def zipBackToRegex(c: Ctx, r: Rexp = ONE) : List[Rexp] = {

   327     c match {

   328         case RootC => r::Nil

   329         case SeqC(m, pr, Nil) => zipBackMem(m, r)

   330         case SeqC(m, pr, unp::Nil) => zipBackMem(m, SEQ(r, unp))

   331         case AltC(m, w) => zipBackMem(m, r)

   332         case StarC(m, vs, r0) => zipBackMem(m, SEQ(r, STAR(r0)))

   333     }

   334 }

   335 

   336 def zipBackMem(m: Mem, r: Rexp = ONE) : List[Rexp] = {

   337     m.parents.flatMap(c => zipBackToRegex(c, r))

   338 }

   339 

   340 //def crystalizeZipper

   341 

   342 mems.clear()

   343 val re1 = ("a" | "aa").%

   344 val re1ss = lex(re1, "aa")

   345 

   346 // drawZippers(re1ss)

   347 // println(actualZipperSize(re1ss))

   348 // println(re1ss)

   349 //val re1S = zipperSimp(re1ss)

   350 //println(actualZipperSize(re1S))

   351 

   352 

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

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

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

   356 

   357 

   358 println(re2res)

   359 

   360 val re2resPlugged = plug_all(re2res)

   361 re2resPlugged.foreach(v => {

   362         val Sequ(Empty, vp) = v

   363         println(vp)

   364 }

   365 )

   366 

   367 // println("remaining regex")

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

   369 

   370 

   371 // val re1ssPlugged = plug_all(re1ss)

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

   373 // re1ssPlugged.foreach(v => {

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

   375 //         //println(vp)

   376 //         println(v)

   377 //     }

   378 // )

   379 // println(mems.size)

   380 //println(mems)

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

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

   383 // println(

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

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

   386 //         case None => ""

   387 //     }

   388 //     )

   389 

   390 // println(re1sPlugged)

   391 //drawZippers(re1s, plugOrNot = false)

   392 // re1s.foreach{

   393 //   re1 => 

   394 //   {

   395 

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

   397 

   398 //   }

   399 // }

   400 

   401