support for limited regexp pattern matching

5 files changed, 130 insertions, 28 deletions

diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala
index 2f03283ed0..9ae5b5b98f 100644
--- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala
+++ b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala
@@ -186,6 +186,8 @@ mixin class CodeFactory requires TransMatcher  {
 */
   def  Equals(left: Tree , right: Tree ): Tree = Apply(Select(left, nme.EQEQ), List(right));
 
+  def  GreaterThan(left: Tree , right: Tree ): Tree = Apply(Select(left, nme.GT), List(right));
+
   //deprecated
   def ThrowMatchError(pos: Int, tpe: Type ) =
     atPos(pos) {
diff --git a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala
index 565e80ea0d..d3d6b9e283 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala
+++ b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala
@@ -44,7 +44,7 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
    */
   def initialize(selector: Tree, owner: Symbol, doBinding: Boolean): Unit = {
 
-    //Console.println("pm.initialize selector.tpe = "+selector.tpe);
+    //Konsole.println("pm.initialize selector.tpe = "+selector.tpe);
 
     /*
     this.mk = new PatternNodeCreator {
@@ -61,14 +61,14 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
     }
     */
     this.root = pConstrPat(selector.pos, selector.tpe.widen);
-    //Console.println("selector.tpe "+selector.tpe);
-    //Console.println("selector.tpe.widen "+selector.tpe.widen);
-    //Console.println("root.symbol "+root.symbol);
-    //Console.println("root.symbol.tpe "+root.symbol.tpe);
+    //Konsole.println("selector.tpe "+selector.tpe);
+    //Konsole.println("selector.tpe.widen "+selector.tpe.widen);
+    //Konsole.println("root.symbol "+root.symbol);
+    //Konsole.println("root.symbol.tpe "+root.symbol.tpe);
     this.root.and = pHeader(selector.pos,
                               selector.tpe.widen,
                               Ident(root.symbol).setType(root.tpe));
-    //Console.println("resultType =  "+resultType);
+    //Konsole.println("resultType =  "+resultType);
     this.owner = owner;
     this.selector = selector;
 
@@ -133,8 +133,12 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
       case Apply(_, args) =>
         if ( isSeqApply(tree.asInstanceOf[Apply])  && !delegateSequenceMatching)
           args(0) match {
-            case ArrayValue(_, ts) => // test array values
-              ts;
+            case av @ ArrayValue(_, ts) => // test array values
+              if(isRightIgnoring(av)) {
+                ts.reverse.drop(1).reverse
+              } else {
+                ts;
+              }
             //case Sequence(ts) =>
             //  ts;
             case _ =>
@@ -173,6 +177,8 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
 	//res;
   }
 
+   //protected var lastSequencePat: PatternNode = null; // hack to optimize sequence matching
+
   protected def patternNode(tree:Tree , header:Header , env: CaseEnv ): PatternNode  = {
     //if(tree!=null) Console.println("patternNode("+tree+","+header+")");
 	//else scala.Predef.error("got null tree in patternNode");
@@ -217,13 +223,16 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
           if (!delegateSequenceMatching) {
             args(0) match {
             //  case Sequence(ts)=>
-              case ArrayValue(_, ts)=>
-                //Console.println("doing pSeqpat ");
-                val res =  pSequencePat(tree.pos, tree.tpe, ts.length);
-                //Console.println("pSeqpat.casted =  "+res.casted);
-                //Console.println("pSeqpat.casted.pos =  "+res.casted.pos);
-                res
-            }
+              case av @ ArrayValue(_, ts)=>
+                if(isRightIgnoring(av)) {
+                  val castedRest = ts.last match {
+                    case b:Bind => b.symbol;
+                    case _      => null
+                  }
+                  pRightIgnoringSequencePat(tree.pos, tree.tpe, castedRest, ts.length-1);
+                } else
+                  pSequencePat(tree.pos, tree.tpe, ts.length);
+                 }
           } else {
             //Console.println("delegating ... ");
             val res = pConstrPat(tree.pos, tree.tpe);
@@ -326,7 +335,9 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
         //case Sequence(ts) =>
         case ArrayValue(_, ts) =>
             if ( !delegateSequenceMatching ) {
-                pSequencePat(tree.pos, tree.tpe, ts.length);
+              //lastSequencePat =
+              pSequencePat(tree.pos, tree.tpe, ts.length);
+              //lastSequencePat
             } else {
                 pSeqContainerPat(tree.pos, tree.tpe, tree);
             }
@@ -342,7 +353,18 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
             i = i + 1
           }
           pAltPat(tree.pos, subroot.and.asInstanceOf[Header]);
-
+/*
+      case Star(Ident(nme.WILDCARD))  =>
+        header.selector match {
+          case Apply(Select(t, apply), arg @ List(litconst)) =>
+            Console.println(t)
+            Console.println(apply)
+            Console.println(litconst)
+            val tree = Apply(Select(Select(t, "toList"), "drop"), arg)
+            throw new OptimizeSequencePattern(tree); // ? has to be caught and rethrown by each bind
+        }
+        // bind the rest /////////////////////////////////////////////////////
+*/
         case _ =>
           if(tree == null)
 		    scala.Predef.error("unit = " + cunit + "; tree = null");
@@ -416,6 +438,7 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
   protected def enter1(pat: Tree, index: Int, target: PatternNode, casted: Symbol,  env: CaseEnv): PatternNode = {
     //System.err.println("enter(" + pat + ", " + index + ", " + target + ", " + casted + ")");
     val patArgs = patternArgs(pat);        // get pattern arguments
+    //System.err.println("patArgs = "+patArgs);
     var curHeader = target.and.asInstanceOf[Header];    // advance one step in intermediate representation
     if (curHeader == null) {                  // check if we have to add a new header
       //assert index >= 0 : casted;
@@ -475,6 +498,8 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
         casted = newCasted;
       case SequencePat(newCasted, len) =>
         casted = newCasted;
+      case RightIgnoringSequencePat(newCasted, _, len) =>
+        casted = newCasted;
       case _ =>
     }
     var i = 0; while(i < pats.length) {
@@ -968,6 +993,39 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An
                          gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true))),
                   toTree(node.and))),
             toTree(node.or, selector.duplicate)));
+
+          case RightIgnoringSequencePat(casted, castedRest, minlen) =>
+          Or(
+            And(
+              And(gen.mkIsInstanceOf(selector.duplicate, node.getTpe()),
+                  GreaterThan(
+                    typed(
+                      Apply(
+                        Select(
+                          gen.mkAsInstanceOf(selector.duplicate,
+                                             node.getTpe(),
+                                             true),
+                          node.getTpe().member(nme.length) /*defs.Seq_length*/),
+                        List())
+                    ),
+                    typed(
+                      Literal(Constant(minlen))
+                    ))),
+              Block(
+                List(
+                  ValDef(casted,
+                         gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true)),
+                  ValDef(castedRest,
+                         Apply(
+                           Select(
+                             Select(
+                               gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true),
+                               "toList"),
+                             "drop"),
+                           List(Literal(Constant(minlen)))))),
+                toTree(node.and))),
+            toTree(node.or, selector.duplicate));
+
           case ConstantPat(value) =>
             //Console.println("selector = "+selector);
             //Console.println("selector.tpe = "+selector.tpe);
diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala b/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala
index 703763f1a7..6c38893a58 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala
+++ b/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala
@@ -21,6 +21,16 @@ mixin class PatternNodeCreator requires (TransMatcher with PatternNodes) {
     node;
   }
 
+  def pRightIgnoringSequencePat(pos: Int, tpe:Type, castedRest1: Symbol, minlen:int) = {
+    //assert (tpe != null);
+    val sym = newVar(Position.FIRSTPOS, tpe);
+    var castedRest = if(castedRest1 != null) castedRest1 else newVar(pos, tpe);
+    val node = new RightIgnoringSequencePat(sym, castedRest, minlen);
+    node.pos = pos;
+    node.tpe = tpe;
+    node;
+  }
+
   def pSeqContainerPat(pos: int, tpe: Type, seqpat:Tree ) = {
     //assert (tpe != null);
     val sym = newVar(Position.NOPOS, tpe);
diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala
index e13db74083..39e9a0b9bb 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala
+++ b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala
@@ -189,6 +189,8 @@ mixin class PatternNodes requires TransMatcher {
            return "ConstrPat(" + casted + ")";
          case SequencePat(casted,  len) =>
            return "SequencePat(" + casted + ", " + len + "...)";
+         case RightIgnoringSequencePat(casted, castedRest,  minlen) =>
+           return "RightIgnoringSequencePat(" + casted + ", " + castedRest + ", "+ minlen + "...)";
          case SeqContainerPat(casted, seqpat) =>
            return "SeqContainerPat(" + casted + ", " + seqpat + ")";
          case ConstantPat(value) =>
@@ -304,7 +306,9 @@ mixin class PatternNodes requires TransMatcher {
   case class ConstantPat(value: Any /*AConstant*/ ) extends PatternNode;
   case class VariablePat(tree: Tree ) extends PatternNode;
   case class AltPat(subheader: Header ) extends PatternNode;
-  case class SequencePat( casted: Symbol,  len:int) extends PatternNode; // only used in PatternMatcher
+  case class SequencePat(casted: Symbol,  len:int) extends PatternNode; // only used in PatternMatcher
+
+  case class RightIgnoringSequencePat(casted: Symbol, castedRest: Symbol, minlen: int) extends PatternNode; //PM
   case class SeqContainerPat(casted: Symbol ,  seqpat: Tree ) extends PatternNode; //   in AlgebraicMatcher
 
   /** the environment for a body of a case
diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
index bca478b0dc..1d67cda80b 100644
--- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
+++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
@@ -11,6 +11,7 @@ abstract class TransMatcher extends transform.Transform
 with PatternNodes
 with CodeFactory
 with PatternMatchers
+with NewMatchers
 with SequenceMatchers
 with AlgebraicMatchers
 with MatcherLabels
@@ -127,6 +128,27 @@ with RightTracers {
     generatedVars;
   }
 
+  protected def isDefault(p: Tree): Boolean = p match {
+    case Bind(_,q)            => isDefault(q);
+    case Ident(nme.WILDCARD)  => true
+    case _                    => false
+  };
+  protected def isDefaultStar(p: Tree): Boolean = p match {
+    case Bind(_,q)                  => isDefaultStar(q);
+    case Star(Ident(nme.WILDCARD))  => true
+    case _                          => false
+  };
+
+  // @todo: this should be isNotRegular :-/ premature opt src of all evil
+  // check special case Seq(_,...,_,_*)
+  protected def isRightIgnoring(p:ArrayValue): Boolean = p match {
+    case ArrayValue(s,trees) =>
+      val it = trees.elements;
+      var c: Tree = null;
+      while(it.hasNext && {c = it.next; isDefault(c)}) {}
+      (!it.hasNext) && isDefaultStar(c)
+  }
+
   class TransMatch extends Transformer {
 
     /** a casedef with sequence subpatterns like
@@ -138,11 +160,11 @@ with RightTracers {
      *  case    .. () .. => val x = Nil; body
      */
     def isRegular(pats:List[CaseDef]): Pair[List[CaseDef],Boolean] = {
-	   var existsReg = false;
-	   var isReg = false;
+      var existsReg = false;
+      var isReg = false;
       var nilVars:List[Symbol] = null;
 
-	  def isRegular1(pat: Tree): Tree = pat match {
+      def isRegular1(pat: Tree): Tree = pat match {
         case Alternative(trees)          =>
           copy.Alternative(pat, trees map { isRegular1 });
 
@@ -160,7 +182,7 @@ with RightTracers {
 		isReg = true; // cause there are ArrayValues now
 		copy.Sequence(pat, trees map { isRegular1 });
 
-	case ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))) =>
+      case ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))) =>
 	//Console.println("OPTIMIZING");
 	//Console.println(pat);
 	//Console.println(pat.tpe);
@@ -172,9 +194,11 @@ with RightTracers {
 	//Console.println(res);
 	res
 
-      case ArrayValue( s, trees )       =>
-	  //Console.println("XXX ArrayValue, trees="+trees);
-        copy.ArrayValue( pat, s, (trees map { isRegular1 }));
+      case av @ ArrayValue( s, trees )       =>
+        if(isRightIgnoring(av))
+          pat
+        else
+          copy.ArrayValue( pat, s, (trees map { isRegular1 }));
 
       case Apply( fn, List(Sequence(List())))      =>
         pat;
@@ -217,11 +241,14 @@ with RightTracers {
 
     def handle(sel:Tree, ocases:List[CaseDef]): Tree = {
 
-
+      // TEMPORARY
+      //new NewMatcher().toIR(sel, ocases)
+      //
       // 1. is there a regular pattern?
 
       val Pair(cases, containsReg) = isRegular(ocases);
 
+
       // @todo: remove unused variables
 
       if(containsReg) {
@@ -238,8 +265,9 @@ with RightTracers {
         }.construct( matcher, cases );
         matcher.tree
 		*/
-                System.out.println("" + sel + " match " + ocases);
-		scala.Predef.error("regular expressions not yet implemented");
+
+        System.out.println("" + sel + " match " + ocases);
+	scala.Predef.error("regular expressions not yet implemented");
       } else {
         val pm = new PatternMatcher();
         pm.initialize(sel, currentOwner, true );