matching stuff

4 files changed, 559 insertions, 0 deletions

diff --git a/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala b/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala
new file mode 100644
index 0000000000..6ec8773c85
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala
@@ -0,0 +1,368 @@
+
+import scala.runtime.matching._ ;
+
+import scala.collection.Set;
+import scala.collection.Map;
+import scala.collection.mutable;
+import scala.collection.immutable;
+
+import scalac.ast._ ;
+import scalac.{Global => scalac_Global}
+import scalac.symtab.Symbol ;
+import scalac.util.Names ;
+
+
+
+package scala.tools.scalac.transformer.matching {
+
+  import PatternInfo.minimalWidth;
+  import TreeInfo.isSequenceValued;
+
+/** generates from a pattern (with variable names v_1,..,v_k)
+ *  a set of regular hedge grammar rules,
+ *  together with an variable index mapping 1,..,k
+ *  @todo: handle x @ z @ p correctly
+ */
+class FullRegularTranslator(global: scalac_Global) {
+
+  /* --- real variables --- */
+
+  /** the grammar that we build up incrementally */
+  var cur:MutableGrammar = _;
+
+  var isSequenceType = false;
+
+  /** counter for variables indices */
+  var varCounter = 0;
+
+  /** counter for test indices */
+  var testCounter = 0;
+
+  /* initialized when Subst is encountered */
+  var iteration:HedgeNT = _;
+
+  /* initialized when Iter is encountered */
+  var iterationEnd:HedgeNT = _;
+
+  /* --- methods --- */
+
+  /** returns a variable index for this variable */
+  def newVar( vble:Symbol ):Int =
+    cur.varMap.get( vble ) match {
+      case Some( x ) => x
+      case None      =>
+        val v = varCounter;
+        varCounter = v + 1;
+        cur.varMap.update( vble, v );
+        v
+    }
+
+  /** returns a test index for this variable */
+    def newTest( test:PatternTest ):Int =
+      cur.invTest.get( test ) match {
+        case Some( x ) => x;
+        case None =>
+          val x = testCounter;
+          testCounter = testCounter + 1;
+          cur.invTest.update( test, x );
+          cur.tests.update( x, test );
+          x
+      }
+
+  /** returns a test index for this variable
+  */
+    def newTest( test:Tree ):Int = {
+      0 // bogus
+    }
+
+
+
+  /**
+    * precondition: p.length > 0
+    */
+  def MakeGrammar( p:Tree* ):Grammar = {
+    val it = p.elements;
+    var k = 0;
+    cur = InitialGrammar.make;
+    while( it.hasNext )
+      translate( it.next, { k = k + 1; k } );
+    cur.toGrammar;
+  }
+
+  protected def translate( p:Tree, k:Int ):unit = {
+
+    this.varCounter = 0;
+    if( isSequenceValued( p ) ) {
+      this.isSequenceType = true;
+      MakeHedgeRule( cur.make.initialHedgeNT, EMPTYHEDGE, emptyVars, p );
+    } else {
+      this.isSequenceType = false;
+      MakeTreeRule( cur.make.initialTreeNT, emptyVars, p );
+    }
+
+    if( global.debug ) {
+      for( val rule <- cur.treeRules ) {
+        global.log( rule.toString() );
+      }
+      for( val rule <- cur.hedgeRules ) {
+        global.log( rule.toString() );
+      }
+      global.log("=== Now Removing Chain Rules ===");
+    } ;
+
+    RemoveChainRules;
+
+    // update variable array with nvariable + 1
+    cur.caseVars.update( k, this.varCounter );
+
+  }
+
+    //val s: mutable.Set[Rule] = new mutable.HashSet[Rule](); /* the grammar */
+
+    //s += AnyTreeRule( ANYTREE );
+
+/* TO BE DONE
+
+Afterwards: Chain rules need not be applied anymore. They only exist with
+    the unique rhs "h0" which produces empty hedge.
+    So, a Chainrule of NT only means that NT can derive the empty hedge
+*/
+
+    def RemoveChainRules: unit = {
+      var replaced = true;
+      while (replaced==true) {
+	replaced = false;
+	for( val rule  <- cur.hedgeRules ) {
+	  rule match {
+            case HedgeChainRule( a, b ) => {
+	      replaced = true;
+              DEBUGPRINT("chain rule"+rule);
+	      cur.hedgeRules -= rule;
+	      val B = b;
+              DEBUGPRINT( "b.nullable " + b.nullable);
+              DEBUGPRINT( "1a.nullable" + a.nullable );
+              a.nullable = a.nullable || b.nullable;
+              DEBUGPRINT( "2a.nullable" + a.nullable );
+	      for( val brule <- cur.hedgeRules ) {
+		brule match {
+		  case HedgeRule( B, Pair( t, h )) =>
+		    cur.hedgeRules += new HedgeRule( a, Pair( t, h ));
+		  case HedgeChainRule( B, h ) =>
+		    cur.hedgeRules += new HedgeChainRule( a, h )
+                  case _ =>
+		}
+	      };
+	    }
+	    case _  =>
+	  }
+
+	}
+      };
+      //Reachables;
+    }
+
+    /*
+    def Reachables: unit = {
+      var reached = new mutable.HashSet[HedgeNT]();
+      reached += InitialHedgeNT;
+      var changed = true;
+      while( changed ) {
+        changed = false;
+        for( val rule <- rules ) {
+          rule match {
+            case HedgeRule( h, Pair(_,h2) ) =>
+              if( !reached.contains(h2) ) {
+                changed = true;
+                reached += h2;
+              }
+            case _ =>
+          }
+        }
+      };
+      for( val rule <- rules ) {
+        rule match {
+          case HedgeRule( h, Pair(_,h2) ) =>
+            if( !reached.contains(h) ) {
+              rules = rules - rule;
+            }
+          case HedgeChainRule(h , _ ) =>
+            if( !reached.contains(h) ) {
+              rules = rules - rule;
+              }
+          case _ =>
+        }
+      }
+    }
+      */
+
+    def sortByWidth( xs:Iterator[Tree] ):List[Tree] = {
+
+
+      def view( x:Pair[Tree,int] ):Ordered[Pair[Tree,int]] =
+        new Ordered[Pair[Tree,int]] with Proxy( x ) {
+          def compareTo [b >: Pair[Tree,int] <% Ordered[b]](that: b): int =
+            that match {
+            case Pair(p:Tree,i:int) =>
+              if( minimalWidth( x._1 ) == minimalWidth( p ) ) {
+                if( x._2 < i ) -1 else
+                  if( x._2 == i ) 0 else 1
+              } else if ( minimalWidth( x._1 ) > minimalWidth( p ) ) {
+                -1
+              } else {
+                1
+              }
+            case _ => error("unexpected");
+          }
+        };
+
+      var mySet = new immutable.TreeSet[Pair[Tree,int]]();
+      var j = 1;
+      for( val p <- xs ) {
+        mySet = mySet + Pair(p,j);
+        j = j + 1;
+      };
+      {for( val Pair(p,i) <- mySet.elements ) yield p}.toList.reverse;
+
+    }
+
+    /* invariant: (in < out) || (out == 0)
+    */
+    def MakeHedgeRule( in:HedgeNT,
+                       out:HedgeNT,
+                       vset: immutable.Set[Int],
+                       it:Iterator[Tree] ):unit = {
+      DEBUGPRINT("MakeHedgeRule("+in+","+out+","+vset+","+it+")");
+      var i = in;
+      if( !it.hasNext ) {
+	cur.hedgeRules += new HedgeChainRule(in, out);
+      } else {
+	while( it.hasNext ) {
+          val pat = it.next;
+	  val nt = if( it.hasNext ) { cur.make.HedgeNT } else { out };
+          MakeHedgeRule( i, nt, vset, pat );
+          i = nt;
+        }
+      }
+                       }
+
+  /*
+  */
+  def MakeHedgeRule( in:HedgeNT, nt:HedgeNT, vset:immutable.Set[Int], pat:Tree):unit =
+    pat match {
+      /*
+      case Point() =>
+	cur.hedgeRules += new HedgeChainRule(in, iteration);
+      cur.hedgeRules += new HedgeChainRule(in, iterationEnd);
+      */
+      case Tree$Sequence( xs ) =>
+	MakeHedgeRule( in, nt, vset, Iterator.fromArray( xs ) );
+
+      case Tree$Alternative( xs  ) =>
+	for( val z <- sortByWidth( Iterator.fromArray( xs ) ) ) {
+	  MakeHedgeRule( in, nt, vset, z );
+	}
+
+      // Star( p )
+      case Tree$Bind(n, p) if TreeInfo.isNameOfStarPattern( n ) =>
+	MakeHedgeRule( in, in, vset, p );
+      cur.hedgeRules += new HedgeChainRule( in, nt );
+
+      // p^[ x ], nt
+      /*
+      case Iter( p, x ) =>
+
+        // sort by width - case 1
+        if( minimalWidth( p ) < minimalWidth( x ) ) {
+          MakeHedgeRule( i, nt, vset, x ); // no iteration ==> x, nt
+        }
+
+      iteration = cur.make.HedgeNT;
+      iterationEnd = cur.make.HedgeNT;
+
+      MakeHedgeRule( i, nt, vset, p );  // unfold p [ # <- x ], nt
+
+      MakeHedgeRule( iteration, EMPTYHEDGE, emptyVars, p );
+      // unfold p [ # <- x + p] $END
+      MakeHedgeRule( iterationEnd, EMPTYHEDGE, emptyVars, x ); // x $END
+      // sort by width - case 2
+      if( minimalWidth( p ) >= minimalWidth( x ) ) {
+        MakeHedgeRule( i, nt, vset, x ); // no iteration ==> x, nt
+      }
+
+      // cleanup
+      iteration = null;
+      iterationEnd = null;
+      */
+      case Tree$Bind( vble, p:Tree ) =>
+        if( isSequenceValued( p ) ) {
+	  MakeHedgeRule( in, nt, vset + newVar( pat.symbol() ), p );
+        } else {
+          try {
+ 	    val trNT = cur.make.TreeNT( vset );
+	    MakeTreeRule( trNT, vset, pat );
+	    cur.hedgeRules += new HedgeRule( in, Pair( trNT, nt ));
+          } catch {
+            case _:WildcardException =>
+	      cur.hedgeRules += new HedgeRule( in, Pair( ANYTREE, nt ));
+          }
+        }
+      case _ =>
+        try {
+	  val trNT = cur.make.TreeNT( vset );
+	  MakeTreeRule( trNT, vset, pat );
+	  cur.hedgeRules += new HedgeRule( in, Pair( trNT, nt ));
+        } catch {
+          case _:WildcardException =>
+	    cur.hedgeRules += new HedgeRule( in, Pair( ANYTREE, nt ));
+
+        }
+    }
+
+
+  def MakeTreeRule( in:TreeNT, vset: immutable.Set[Int], pat:Tree):unit = {
+    DEBUGPRINT("MakeTreeRule("+in+","+vset+","+pat+")");
+    pat match {
+      // WildcardTree()
+      case Tree$Ident( Names.PATTERN_WILDCARD ) =>
+        if( vset.isEmpty )
+          throw new WildcardException(); // OPTIMIZATION to collapse _ rules
+        else
+          cur.treeRules += new AnyTreeRule( in );
+      // WildcardNode( x @ _* )
+      case Tree$Apply( Tree$Ident( Names.PATTERN_WILDCARD ), xs ) =>
+	{
+	  val Children = cur.make.HedgeNT;
+          cur.treeRules += new AnyNodeRule( in, Children );
+	  MakeHedgeRule( Children, EMPTYHEDGE, emptyVars, Iterator.fromArray( xs ));
+	}
+      // Node( label:String, x @ _* ) => //p.type
+      case Tree$Apply( theTest, xs ) =>
+        val test = newTest( theTest ); //p.type
+        val childrenNT = cur.make.HedgeNT; // make a new NT
+        cur.treeRules += new TreeRule(in, new Pair( test, childrenNT ));
+        MakeHedgeRule( childrenNT, EMPTYHEDGE, emptyVars, Iterator.fromArray( xs ));
+
+      case Tree$Alternative( xs ) => // is tree valued
+        for(val pat<-Iterator.fromArray( xs ))
+          MakeTreeRule( in, vset, pat );
+
+      case Tree$Bind( _, p:Tree ) =>
+        in.vset = in.vset + newVar( pat.symbol() );
+        MakeTreeRule( in, in.vset, p );
+
+      case _ => //DEBUGPRINT("error, we found "+p.getClass());
+    }
+  } // end MakeTreeRule
+
+
+  /* misc stuff */
+
+  def DEBUGPRINT( s:String ):unit =  // misc DEBUG
+    if (global.debug) Console.println( s );
+
+  class WildcardException extends Exception ;   // backtrack
+
+  final val emptyVars = new immutable.TreeSet[Int](); // convenience
+
+}
+}
diff --git a/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala b/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala
new file mode 100644
index 0000000000..1ec9a6b30d
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala
@@ -0,0 +1,126 @@
+
+import scala.collection.immutable;
+import scala.collection.mutable;
+import scala.runtime.matching._;
+
+import scalac.symtab.Symbol;
+
+package scala.tools.scalac.transformer.matching {
+
+object InitialGrammar {
+  /** returns an initial grammar, with any tree rule and any hedge rule */
+  def make:MutableGrammar = {
+    val initialTreeRules = new mutable.HashSet[TRule]();
+    initialTreeRules += AnyTreeRule( ANYTREE );
+    val initialHedgeRules = new mutable.HashSet[HRule]();
+    val vars = new mutable.HashMap[Int,Int]();
+    val tests = new mutable.HashMap[Int,PatternTest]() ;
+    val z = new MutableGrammar(
+      initialTreeRules,
+      initialHedgeRules,
+      vars,
+      tests,
+      new NonTermFactory
+    );
+    z.varMap = new mutable.HashMap[Symbol, Int]();
+    z.invTest = new mutable.HashMap[PatternTest, Int]();
+    z
+  }
+}
+
+
+/** compile-time representation of patterns. This class treats all variable
+ *  indices as sequence variables.
+ */
+case class MutableGrammar( treeRules:mutable.Set[TRule],
+                           hedgeRules:mutable.Set[HRule],
+                           caseVars:mutable.Map[Int,Int],
+                           tests:mutable.Map[int,PatternTest],
+                           make:NonTermFactory )
+{
+
+  var invTest:mutable.Map[PatternTest,int] = _;
+
+  /** from variable names to indices. */
+  var varMap:mutable.Map[Symbol, Int] = _;
+
+  final def hedgeRulesToString:String = {
+    hedgeRules.foldLeft ("") {
+      (s:String,r:Rule) => s + (r match {
+        case HedgeRule( h, _ ) if ( make.hedgeInitials contains h ) => "*"
+        case _ => " "
+      }) + r.toString() + "\n"
+    } ;
+  }
+
+  final def treeRulesToString:String = {
+    treeRules.foldLeft ("") {
+      (s:String,r:Rule) => s + (r match {
+        case TreeRule( t, _ ) if ( make.treeInitials contains t ) => "*"
+        case _ => " "
+      }) + r.toString() + "\n"
+    } ;
+  }
+
+  def toString:String = {
+    val sb = new StringBuffer();
+    sb.append( { if( treeRules.isEmpty )
+      "Set of rules is EMPTY.\n" else treeRulesToString });
+    sb.append( { if( hedgeRules.isEmpty )
+      "Set of rules is EMPTY.\n" else hedgeRulesToString });
+
+    sb.append( "hedgeInitials:"+make.hedgeInitials );
+    sb.append( "treeInitials:"+make.treeInitials );
+
+    //sb.append( "\nvariables :"+( caseVars( 0 ).map { debugVarMapping }) );
+    sb.toString()
+  }
+
+  protected def add( i:Int, r:Rule, m:immutable.TreeMap[Int,immutable.Set[Rule]] ) =
+    m.update( i, m.get( i ) match {
+      case Some( s ) => s + r;
+      case None => immutable.ListSet.Empty[Rule] + r;
+    });
+
+
+
+  /** converts this grammar in a immutable grammar
+  */
+  def toGrammar:Grammar = {
+    val treeTransitions:immutable.TreeMap[Int,immutable.Set[Rule]] = {
+      var tmp =
+        immutable.TreeMap.Empty[Int,immutable.Set[Rule]];
+      treeRules.foreach { treeRule => treeRule match {
+        case AnyTreeRule( t ) => tmp = add( t.i, treeRule, tmp );
+        case AnyNodeRule( t, _ ) => tmp = add( t.i, treeRule, tmp )
+        case TreeRule( t, _ ) => tmp = add( t.i, treeRule, tmp )
+      }};
+      tmp
+    };
+    val hedgeTransitions:immutable.TreeMap[Int,immutable.Set[Rule]] = {
+      var tmp =
+        immutable.TreeMap.Empty[Int,immutable.Set[Rule]];
+      hedgeRules.foreach { hedgeRule => hedgeRule match {
+        case HedgeRule( h, _ ) => tmp = add( h.i, hedgeRule, tmp );
+        case HedgeChainRule( h, _ ) => tmp = add( h.i, hedgeRule, tmp );
+      }};
+      // to maintain assumption that every hedge nt is present
+      tmp.update( 0, immutable.ListSet.Empty[Rule] );
+    };
+    val theCaseVars = new Array[Int]( caseVars.size );
+    for( val k <- caseVars.keys ) {
+      theCaseVars( k ) = caseVars( k );
+    }
+    new Grammar( treeTransitions, hedgeTransitions, theCaseVars ) {
+      val treeInitials = make.treeInitials;
+      val hedgeInitials = make.hedgeInitials;
+      // @todo
+      def test( test:int, inp:Any ):boolean = {
+        false;
+      };
+    }
+  }
+
+}
+
+}
diff --git a/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala b/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala
new file mode 100644
index 0000000000..db6a6cd352
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala
@@ -0,0 +1,53 @@
+
+import scalac.ast._ ;
+import scalac.util.Names ;
+
+package scala.tools.scalac.transformer.matching {
+
+  /** some properties of pattern */
+  object PatternInfo {
+
+
+    /** returns width */
+    private def getLowerBoundWidth( it:Iterator[Tree] ):Int = {
+      if( !it.hasNext ) 0 else {
+        var wid = minimalWidth( it.next );
+        for( val h <- it ) {
+          val hw = minimalWidth( h );
+          if( hw < wid ) {
+            wid = hw
+          }
+        }
+        wid
+      }
+    }
+
+    /** @todo translate this from ems pattern
+    */
+    def minimalWidth( pat:Tree ):Int = pat match {
+      case Tree$Alternative( choices ) => 1 // bogus
+
+      // WildcardTree pattern _
+      case Tree$Ident( Names.PATTERN_WILDCARD ) => 1
+
+      // Node pattern t ( ps )    // works also for WildcardNode pattern
+      case Tree$Apply( _, _  ) => 1
+
+      // p | ... | p
+      case Tree$Alternative( ps ) =>
+        getLowerBoundWidth( Iterator.fromArray( ps ) );
+
+      // p1...pN
+      case Tree$Sequence( ps ) =>
+        Iterator.fromArray( ps ).foldLeft (0) {
+          (s:int,x:Tree) => s + minimalWidth( x )
+        }
+
+      case Tree$Bind( n, p ) => 1
+
+      case _                    => 0
+
+    }
+  }
+
+}
diff --git a/sources/scala/tools/scalac/transformer/matching/PatternTest.scala b/sources/scala/tools/scalac/transformer/matching/PatternTest.scala
new file mode 100644
index 0000000000..c93468eed0
--- /dev/null
+++ b/sources/scala/tools/scalac/transformer/matching/PatternTest.scala
@@ -0,0 +1,12 @@
+package scala.tools.scalac.transformer.matching ;
+
+abstract class PatternTest ;
+
+/** test for patterns _:T      */
+case class TypeTest extends PatternTest ;
+
+/** test for patterns A(...)   */
+case class CaseTest extends PatternTest ;
+
+/** test for constant patterns */
+case class EqTest extends PatternTest ;