Some trees make a nice smooth transition into a...

Some trees make a nice smooth transition into a Pattern class, others
fight tooth and nail. Partway there.

3 files changed, 165 insertions, 100 deletions

diff --git a/src/compiler/scala/tools/nsc/matching/Matrix.scala b/src/compiler/scala/tools/nsc/matching/Matrix.scala
index d02576208e..edd6d60fab 100644
--- a/src/compiler/scala/tools/nsc/matching/Matrix.scala
+++ b/src/compiler/scala/tools/nsc/matching/Matrix.scala
@@ -16,6 +16,64 @@ trait Matrix extends PatternOptimizer {
   import analyzer.Typer
   import CODE._
 
+  /** Translation of match expressions.
+   *
+   *  `p':  pattern
+   *  `g':  guard
+   *  `bx': body index
+   *
+   *   internal representation is (tvars:List[Symbol], rows:List[Row])
+   *
+   *         tmp1      tmp_n
+   *    Row( p_11  ...  p_1n   g_1  b_1 ) + subst
+   *
+   *    Row( p_m1  ...  p_mn   g_m  b_m ) + subst
+   *
+   * Implementation based on the algorithm described in
+   *
+   *   "A Term Pattern-Match Compiler Inspired by Finite Automata Theory"
+   *   Mikael Pettersson
+   *   ftp://ftp.ida.liu.se/pub/labs/pelab/papers/cc92pmc.ps.gz
+   *
+   *  @author Burak Emir
+   */
+
+  /** "The Mixture Rule"
+
+        {v=pat1, pats1 .. } {q1}
+  match {..               } {..}
+        {v=patn, patsn .. } {qn}
+
+  The is the real work-horse of the algorithm. There is some column whose top-most pattern is a
+  constructor. (Forsimplicity, itisdepicted above asthe left-most column, but anycolumn will do.)
+  The goal is to build a test state with the variablevand some outgoing arcs (one for each construc-
+  tor and possibly a default arc). Foreach constructorcin the selected column, its arc is defined as
+  follows:
+
+  Let {i1,...,ij} be the rows-indices of the patterns in the column that match c. Since the pat-
+  terns are viewed as regular expressions, this will be the indices of the patterns that either
+  have the same constructor c, or are wildcards.
+
+  Let {pat1,...,patj} be the patterns in the column corresponding to the indices computed
+  above, and let nbe the arity of the constructor c, i.e. the number of sub-patterns it has. For
+  eachpati, its n sub-patterns are extracted; if pat i is a wildcard, nwildcards are produced
+  instead, each tagged with the right path variable. This results in a pattern matrix with n
+  columns and j rows. This matrix is then appended to the result of selecting, from each col-
+  umn in the rest of the original matrix, those rows whose indices are in {i1,...,ij}. Finally
+  the indices are used to select the corresponding final states that go with these rows. Note
+  that the order of the indices is significant; selected rows do not change their relative orders.
+  The arc for the constructor c is now defined as (c’,state), where c’ is cwith any
+  immediate sub-patterns replaced by their path variables (thus c’ is a simple pattern), and
+  state is the result of recursively applying match to the new matrix and the new sequence
+  of final states.
+
+  Finally, the possibility for matching failure is considered. If the set of constructors is exhaustive,
+  then no more arcs are computed. Otherwise, a default arc(_,state)is the last arc. If there are
+  any wildcard patterns in the selected column, then their rows are selected from the rest of the
+  matrix and the final states, and the state is the result of applying match to the new matrix and
+  states. Otherwise,the error state is used after its reference count has been incremented.
+  **/
+
   case class MatrixInit(
     roots: List[Symbol],
     cases: List[CaseDef],
diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
index 9fc2ecb379..f39a2d0f08 100644
--- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
+++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
@@ -18,27 +18,6 @@ import MatchUtil._
 import annotation.elidable
 import Function.tupled
 
-/** Translation of match expressions.
- *
- *  `p':  pattern
- *  `g':  guard
- *  `bx': body index
- *
- *   internal representation is (tvars:List[Symbol], rows:List[Row])
- *
- *         tmp1      tmp_n
- *    Row( p_11  ...  p_1n   g_1  b_1 ) + subst
- *
- *    Row( p_m1  ...  p_mn   g_m  b_m ) + subst
- *
- * Implementation based on the algorithm described in
- *
- *   "A Term Pattern-Match Compiler Inspired by Finite Automata Theory"
- *   Mikael Pettersson
- *   ftp://ftp.ida.liu.se/pub/labs/pelab/papers/cc92pmc.ps.gz
- *
- *  @author Burak Emir
- */
 trait ParallelMatching extends ast.TreeDSL
       with Matrix
       with Patterns
@@ -109,21 +88,14 @@ trait ParallelMatching extends ast.TreeDSL
     /** the injection here handles alternatives and unapply type tests */
     final def make(tvars: List[Symbol], row1: List[Row]): Rep = {
       def classifyPat(opat: Pattern, j: Int): Pattern = {
+        def testVar = tvars(j)
+
         // @pre for doUnapplySeq: is not right-ignoring (no star pattern) ; no exhaustivity check
         def doUnapplySeq(tptArg: Tree, xs: List[Tree]) = {
-          tvars(j) setFlag Flags.TRANS_FLAG
+          testVar setFlag Flags.TRANS_FLAG
 
           opat rebindTo normalizedListPattern(xs, tptArg.tpe)
         }
-
-        def doUnapplyApply(ua: UnApply, fn: Tree) = {
-          val MethodType(List(arg, _*), _) = fn.tpe
-          val npat =
-            if (tvars(j).tpe <:< arg.tpe) ua
-            else Typed(ua, TypeTree(arg.tpe)) setType arg.tpe
-
-          opat rebindTo npat
-        }
         def doValMatch(x: Tree, fn: Tree) = {
           val p = Pattern(x)
 
@@ -153,15 +125,17 @@ trait ParallelMatching extends ast.TreeDSL
         // pattern match before the final curtain falls.
         val f = List[PartialFunction[Tree, Pattern]](
           { case _: Alternative                       => opat } ,
-          { case Typed(p @ Stripped(_: UnApply), tpt) => if (tvars(j).tpe <:< tpt.tpe) opat rebindTo p else opat } ,
+          { case _: Typed                             => opat simplify testVar } ,
           { case x if doReturnOriginal(x)             => opat } ,
+          // This busts things for now
+          // { case _: Ident                             => opat.simplify() } ,
           { case _: Ident | _: Select                 => opat.rebindToEqualsCheck() } ,
           { case _: This                              => opat } ,
           { case UnapplySeq(tptArg, xs)               => doUnapplySeq(tptArg, xs) } ,
-          { case ua @ UnApply(Apply(fn, _), _)        => doUnapplyApply(ua, fn) } ,
+          { case UnApply(Apply(fn, _), _)             => opat simplify testVar } ,
           { case x @ Apply_Function(fn)               => doValMatch(x, fn) } ,
-          { case Apply_Value(pre, sym)                => opat rebindToEmpty mkEqualsRef(singleType(pre, sym)) } ,
-          { case Apply_CaseClass(tpe, args)           => if (args.isEmpty) opat rebindToEmpty tpe else opat } ,
+          { case Apply_Value(_, _)                    => opat simplify testVar } ,
+          { case Apply_CaseClass(_, _)                => opat.simplify() } ,
           { case x                                    => abort("Unexpected pattern: " + x.getClass + " => " + x) }
         ) reduceLeft (_ orElse _)
 
@@ -265,7 +239,7 @@ trait ParallelMatching extends ast.TreeDSL
         def unapply(x: Patterns) = if (x.scrut.isSimple) x.extractSimpleSwitch else None
       }
 
-      def mkRule(rest: Rep): RuleApplication =
+      def mkRule(rest: Rep): RuleApplication = {
         logAndReturn("mkRule: ", head.boundTree match {
             case x if isEquals(x.tpe)                 => new MixEquals(this, rest)
             case x: ArrayValue if isRightIgnoring(x)  => new MixSequenceStar(this, rest)
@@ -277,7 +251,14 @@ trait ParallelMatching extends ast.TreeDSL
             }
           }
         )
-    }
+      }
+    } // Patterns
+
+    /** picks which rewrite rule to apply
+     *  @precondition: column does not contain alternatives
+     */
+    def MixtureRule(scrut: Scrutinee, column: List[Pattern], rest: Rep): RuleApplication =
+      Patterns(scrut, column) mkRule rest
 
     /**
      * Class encapsulating a guard expression in a pattern match:
@@ -290,47 +271,7 @@ trait ParallelMatching extends ast.TreeDSL
     }
     val NoGuard = Guard(EmptyTree)
 
-    /** "The Mixture Rule"
-
-          {v=pat1, pats1 .. } {q1}
-    match {..               } {..}
-          {v=patn, patsn .. } {qn}
-
-    The is the real work-horse of the algorithm. There is some column whose top-most pattern is a
-    constructor. (Forsimplicity, itisdepicted above asthe left-most column, but anycolumn will do.)
-    The goal is to build a test state with the variablevand some outgoing arcs (one for each construc-
-    tor and possibly a default arc). Foreach constructorcin the selected column, its arc is defined as
-    follows:
-
-    Let {i1,...,ij} be the rows-indices of the patterns in the column that match c. Since the pat-
-    terns are viewed as regular expressions, this will be the indices of the patterns that either
-    have the same constructor c, or are wildcards.
-
-    Let {pat1,...,patj} be the patterns in the column corresponding to the indices computed
-    above, and let nbe the arity of the constructor c, i.e. the number of sub-patterns it has. For
-    eachpati, its n sub-patterns are extracted; if pat i is a wildcard, nwildcards are produced
-    instead, each tagged with the right path variable. This results in a pattern matrix with n
-    columns and j rows. This matrix is then appended to the result of selecting, from each col-
-    umn in the rest of the original matrix, those rows whose indices are in {i1,...,ij}. Finally
-    the indices are used to select the corresponding final states that go with these rows. Note
-    that the order of the indices is significant; selected rows do not change their relative orders.
-    The arc for the constructor c is now defined as (c’,state), where c’ is cwith any
-    immediate sub-patterns replaced by their path variables (thus c’ is a simple pattern), and
-    state is the result of recursively applying match to the new matrix and the new sequence
-    of final states.
-
-    Finally, the possibility for matching failure is considered. If the set of constructors is exhaustive,
-    then no more arcs are computed. Otherwise, a default arc(_,state)is the last arc. If there are
-    any wildcard patterns in the selected column, then their rows are selected from the rest of the
-    matrix and the final states, and the state is the result of applying match to the new matrix and
-    states. Otherwise,the error state is used after its reference count has been incremented.
-    **/
-
-    /** picks which rewrite rule to apply
-     *  @precondition: column does not contain alternatives
-     */
-    def MixtureRule(scrut: Scrutinee, column: List[Pattern], rest: Rep): RuleApplication =
-      Patterns(scrut, column) mkRule rest
+    /***** Rule Applications *****/
 
     sealed abstract class RuleApplication {
       def pats: Patterns
@@ -476,7 +417,7 @@ trait ParallelMatching extends ast.TreeDSL
       def newVarCapture(pos: Position, tpe: Type) =
         newVar(pos, tpe, flags = scrut.flags)
 
-      /** returns (unapply-call, success-rep, optional fail-rep*/
+    /** returns (un)apply-call, success-rep, optional fail-rep */
       final def getTransition(): Branch[UnapplyCall] = {
         val unapplyRes  = newVarCapture(ua.pos, app.tpe)
         val rhs         = Apply(fxn, scrut.id :: trailingArgs) setType unapplyRes.tpe
@@ -826,6 +767,8 @@ trait ParallelMatching extends ast.TreeDSL
       }
     }
 
+  /*** States, Rows, Etc. ***/
+
     case class Row(pat: List[Pattern], subst: Bindings, guard: Guard, bx: Int) {
       def insert(h: Pattern)              = copy(pat = h :: pat)
       def insert(hs: List[Pattern])       = copy(pat = hs ::: pat)    // prepends supplied tree
@@ -916,7 +859,6 @@ trait ParallelMatching extends ast.TreeDSL
       def isReachedTwice = referenceCount > 1
     }
 
-
     case class Combo(index: Int, sym: Symbol) {
       // is this combination covered by the given pattern?
       def isCovered(p: Pattern) = cond(p.tree) {
diff --git a/src/compiler/scala/tools/nsc/matching/Patterns.scala b/src/compiler/scala/tools/nsc/matching/Patterns.scala
index caa6dbf696..2bc76b57f1 100644
--- a/src/compiler/scala/tools/nsc/matching/Patterns.scala
+++ b/src/compiler/scala/tools/nsc/matching/Patterns.scala
@@ -6,6 +6,8 @@
 package scala.tools.nsc
 package matching
 
+import symtab.Flags
+
 /**
  * Simple pattern types:
  *
@@ -37,9 +39,12 @@ trait Patterns extends ast.TreeDSL {
   // Fresh patterns
   final def emptyPatterns(i: Int): List[Pattern] = List.fill(i)(NoPattern)
 
-  // A fresh, empty pattern
+  // An empty pattern
   def NoPattern = WildcardPattern()
 
+  // The constant null pattern
+  def NullPattern = Pattern(NULL)
+
   // 8.1.1
   case class VariablePattern(tree: Ident) extends Pattern {
     override def irrefutableFor(tpe: Type) = true
@@ -56,21 +61,46 @@ trait Patterns extends ast.TreeDSL {
     private val Typed(expr, tpt) = tree
 
     override def irrefutableFor(tpe: Type) = tpe <:< tree.tpe
+    override def simplify(testVar: Symbol) = Pattern(expr) match {
+      case ExtractorPattern(ua) if testVar.tpe <:< tpt.tpe  => this rebindTo expr
+      case _                                                => this
+    }
   }
 
   // 8.1.3
   case class LiteralPattern(tree: Literal) extends Pattern { }
 
   // 8.1.4
-  case class StableIdPattern(tree: Ident) extends Pattern { }
+  case class StableIdPattern(tree: Ident) extends Pattern {
+    override def simplify(testVar: Symbol) = rebindToEqualsCheck()
+  }
+
+  // 8.1.4 (b)
+  case class SelectPattern(tree: Select) extends Pattern {
+    // override def simplify(testVar: Symbol) =
+    //   this rebindToEmpty mkEqualsRef(singleType(pre, sym))
+  }
 
   // 8.1.4 (b)
 
   // 8.1.5
   case class ConstructorPattern(tree: Apply) extends ApplyPattern {
+    require(fn.isType)
+
+    override def simplify(testVar: Symbol) =
+      if (args.isEmpty) this rebindToEmpty tree.tpe
+      else this
+
     // XXX todo
     // override def irrefutableFor(tpe: Type) = false
   }
+  // XXX temp
+  case class ApplyValuePattern(tree: Apply) extends ApplyPattern {
+    require(!fn.isType)
+
+    override def simplify(testVar: Symbol) =
+      this rebindToEmpty mkEqualsRef(singleType(prefix, sym))
+  }
 
   // 8.1.6
   case class TuplePattern(tree: Apply) extends ApplyPattern {
@@ -82,18 +112,32 @@ trait Patterns extends ast.TreeDSL {
   case class ExtractorPattern(tree: UnApply) extends Pattern {
     private val UnApply(Apply(fn, _), args) = tree
     private val MethodType(List(arg, _*), _) = fn.tpe
+    private def uaTyped = Typed(tree, TypeTree(arg.tpe)) setType arg.tpe
 
-    def uaTyped = Typed(tree, TypeTree(arg.tpe)) setType arg.tpe
+    override def simplify(testVar: Symbol) =
+      if (testVar.tpe <:< arg.tpe) this
+      else this rebindTo uaTyped
   }
 
-  // 8.1.8
+  // 8.1.8 (unapplySeq calls)
+  case class SequenceExtractorPattern(tree: UnApply) extends Pattern {
+    private val UnApply(
+      Apply(TypeApply(Select(_, nme.unapplySeq), List(tptArg)), _),
+      List(ArrayValue(_, elems))
+    ) = tree
+
+    // @pre: is not right-ignoring (no star pattern) ; no exhaustivity check
+    override def simplify(testVar: Symbol) = {
+      testVar setFlag Flags.TRANS_FLAG
+      this rebindTo normalizedListPattern(elems, tptArg.tpe)
+    }
+  }
+
+  // 8.1.8 (b) (literal ArrayValues)
   case class SequencePattern(tree: ArrayValue) extends Pattern { }
 
-  // 8.1.8 (b)
-  case class SequenceStarPattern(tree: ArrayValue) extends Pattern {
-    // def removeStar(xs: List[Pattern]): List[Pattern] =
-    //   xs.init ::: List(Pattern(makeBind(xs.last.boundVariables, WILD(scrut.seqType))))
-  }
+  // // 8.1.8 (b)
+  case class SequenceStarPattern(tree: ArrayValue) extends Pattern { }
 
   // 8.1.9
   // InfixPattern ... subsumed by Constructor/Extractor Patterns
@@ -101,14 +145,13 @@ trait Patterns extends ast.TreeDSL {
   // 8.1.10
   case class AlternativePattern(tree: Alternative) extends Pattern {
     private val Alternative(subtrees) = tree
-    lazy val subpatterns = subtrees map Pattern.apply
+    override def subpatterns(pats: MatchMatrix#Patterns) = subtrees map Pattern.apply
   }
 
   // 8.1.11
   // XMLPattern ... for now, subsumed by SequencePattern, but if we want
   //   to make it work right, it probably needs special handling.
 
-
   // XXX - temporary pattern until we have integrated every tree type.
   case class MiscPattern(tree: Tree) extends Pattern {
     // println("Resorted to MiscPattern: %s/%s".format(tree, tree.getClass))
@@ -127,16 +170,25 @@ trait Patterns extends ast.TreeDSL {
       case x: Apply             => ApplyPattern(x)
       case x: Typed             => TypedPattern(x)
       case x: Literal           => LiteralPattern(x)
-      case x: UnApply           => ExtractorPattern(x)
+      case x: UnApply           => UnapplyPattern(x)
       case x: Ident             => if (isVarPattern(x)) VariablePattern(x) else StableIdPattern(x)
       case x: ArrayValue        => if (isRightIgnoring(x)) SequenceStarPattern(x) else SequencePattern(x)
-      case x: Select            => MiscPattern(x) // XXX
+      case x: Select            => SelectPattern(x)
       case x: Star              => MiscPattern(x) // XXX
       case _                    => abort("Unknown Tree reached pattern matcher: %s/%s".format(tree, tree.getClass))
     }
     def unapply(other: Pattern): Option[Tree] = Some(other.tree)
   }
 
+  object UnapplyPattern {
+    def apply(x: UnApply): Pattern = {
+      x match {
+        case UnapplySeq(_, _) => SequenceExtractorPattern(x)
+        case _                => ExtractorPattern(x)
+      }
+    }
+  }
+
   // right now a tree like x @ Apply(fn, Nil) where !fn.isType
   // is handled by creating a singleton type:
   //
@@ -159,23 +211,36 @@ trait Patterns extends ast.TreeDSL {
         if (isTupleType(fn.tpe)) TuplePattern(x)
         else ConstructorPattern(x)
       }
-      else if (args.isEmpty) fn match {
-        case _  => ConstructorPattern(x)  // XXX
-        // case x: Ident => StableIdPattern(x)
-        // case x        => MiscPattern(x)
-      }
+      else if (args.isEmpty) ApplyValuePattern(x)
       else abort("Strange apply: %s/%s".format(x))
     }
   }
 
   sealed abstract class ApplyPattern extends Pattern {
     protected lazy val Apply(fn, args) = tree
+    private def isCaseClass = tree.tpe.typeSymbol hasFlag Flags.CASE
+
+    override def subpatterns(pats: MatchMatrix#Patterns): List[Pattern] =
+      if (isConstructorPattern && isCaseClass) {
+        if (pats.isCaseHead) args map Pattern.apply
+        else pats.dummyPatterns
+      }
+      else if (isConstructorPattern && !args.isEmpty) abort("Strange Apply")
+      else pats.dummyPatterns
 
     def isConstructorPattern = fn.isType
   }
-
+  // trait SimplePattern extends Pattern {
+  //   def simplify(testVar: Symbol): Pattern = this
+  // }
   sealed abstract class Pattern {
     val tree: Tree
+    // The logic formerly in classifyPat, returns either a simplification
+    // of this pattern or identity.
+    def simplify(testVar: Symbol): Pattern = this
+    def simplify(): Pattern = simplify(NoSymbol)
+
+    def subpatterns(pats: MatchMatrix#Patterns): List[Pattern] = Nil
 
     // 8.1.13
     // A pattern p is irrefutable for type T if any of the following applies:
@@ -261,7 +326,7 @@ trait Patterns extends ast.TreeDSL {
       if (_boundTree == null) Pattern(tree)
       else Pattern(tree) withBoundTree _boundTree
 
-    override def toString() = "Pattern(%s, %s)".format(tree, boundVariables)
+    // override def toString() = "Pattern(%s, %s)".format(tree, boundVariables)
     override def equals(other: Any) = other match {
       case x: Pattern => this.boundTree == x.boundTree
       case _          => super.equals(other)