A wholesale reversion of the pattern matcher to...

A wholesale reversion of the pattern matcher to r21939, motivated by
the appearance of #3578. Closes #3578, reopens #2800, #3050. Review by
moors. (I can't keep saying "no review" when every move I make in here
seems to break something.)

6 files changed, 74 insertions, 58 deletions

diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
index 3438c77e44..77997c4565 100644
--- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
+++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
@@ -7,6 +7,7 @@
 package scala.tools.nsc
 package matching
 
+import util.Position
 import transform.ExplicitOuter
 import symtab.Flags
 import collection._
@@ -170,7 +171,7 @@ trait ParallelMatching extends ast.TreeDSL
       def tail = ps.tail
       def size = ps.length
 
-      def headType = head.tpe
+      def headType = head.necessaryType
       def isCaseHead = head.isCaseClass
       private val dummyCount = if (isCaseHead) headType.typeSymbol.caseFieldAccessors.length else 0
       def dummies = emptyPatterns(dummyCount)
@@ -190,10 +191,9 @@ trait ParallelMatching extends ast.TreeDSL
         }
       }
 
-      if (settings.Xmigration28.value) {
-        for (p <- ps ; if isArraySeqTest(scrut.tpe, p.tpe)) {
-          val reportPos = if (p.tree.pos.isDefined) p.tree.pos else scrut.pos
-          cunit.warning(reportPos, "An Array will no longer match as Seq[_].")
+      object TypedUnapply {
+        def unapply(x: Tree): Option[Boolean] = condOpt(x) {
+          case Typed(UnapplyParamType(tpe), tpt) => !(tpt.tpe <:< tpe)
         }
       }
 
@@ -575,10 +575,10 @@ trait ParallelMatching extends ast.TreeDSL
 
         for ((pattern, j) <- pmatch.pzip()) {
           // scrutinee, head of pattern group
-          val (s, p) = (pattern.tpe, head.tpe)
+          val (s, p) = (pattern.tpe, head.necessaryType)
 
-          def isEquivalent  = head.tpe =:= pattern.tpe
-          def isObjectTest  = pattern.isObject && (p =:= pattern.tpe)
+          def isEquivalent  = head.necessaryType =:= pattern.tpe
+          def isObjectTest  = pattern.isObject && (p =:= pattern.necessaryType)
 
           def sMatchesP = matches(s, p)
           def pMatchesS = matches(p, s)
@@ -589,7 +589,7 @@ trait ParallelMatching extends ast.TreeDSL
           def passr()                                                           = Some( No(j, pattern))
 
           def typed(pp: Tree) = passl(ifEquiv(Pattern(pp)))
-          def subs()          = passl(ifEquiv(NoPattern), pattern expandToArity head.arity)
+          def subs()          = passl(ifEquiv(NoPattern), pattern subpatterns pmatch)
 
           val (oneY, oneN) = pattern match {
             case Pattern(LIT(null), _) if !(p =:= s)        => (None, passr)      // (1)
diff --git a/src/compiler/scala/tools/nsc/matching/PatternBindings.scala b/src/compiler/scala/tools/nsc/matching/PatternBindings.scala
index 82bddb2013..83fd3a9608 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternBindings.scala
+++ b/src/compiler/scala/tools/nsc/matching/PatternBindings.scala
@@ -104,7 +104,10 @@ trait PatternBindings extends ast.TreeDSL
 
     // Like rebindToEqualsCheck, but subtly different.  Not trying to be
     // mysterious -- I haven't sorted it all out yet.
-    def rebindToObjectCheck(): Pattern = rebindToType(mkEqualsRef(atomicTpe), atomicTpe)
+    def rebindToObjectCheck(): Pattern = {
+      val sType = sufficientType
+      rebindToType(mkEqualsRef(sType), sType)
+    }
 
     /** Helpers **/
     private def wrapBindings(vs: List[Symbol], pat: Tree): Tree = vs match {
diff --git a/src/compiler/scala/tools/nsc/matching/Patterns.scala b/src/compiler/scala/tools/nsc/matching/Patterns.scala
index 7621c1c2f3..a135655b9d 100644
--- a/src/compiler/scala/tools/nsc/matching/Patterns.scala
+++ b/src/compiler/scala/tools/nsc/matching/Patterns.scala
@@ -89,7 +89,7 @@ trait Patterns extends ast.TreeDSL {
     // require (!isVarPattern(fn) && args.isEmpty)
     val ident @ Ident(name) = fn
 
-    override def atomicTpe = Pattern(ident).equalsCheck
+    override def sufficientType = Pattern(ident).equalsCheck
     override def simplify(pv: PatternVar) = this.rebindToObjectCheck()
     override def description = "Id(%s)".format(name)
   }
@@ -98,7 +98,7 @@ trait Patterns extends ast.TreeDSL {
     require (args.isEmpty)
     val Apply(select: Select, _) = tree
 
-    override def atomicTpe = mkSingletonFromQualifier
+    override def sufficientType = mkSingletonFromQualifier
     override def simplify(pv: PatternVar) = this.rebindToObjectCheck()
     override def description = backticked match {
       case Some(s)  => "this." + s
@@ -117,7 +117,7 @@ trait Patterns extends ast.TreeDSL {
   case class ObjectPattern(tree: Apply) extends ApplyPattern {  // NamePattern?
     require(!fn.isType && isModule)
 
-    override def atomicTpe = tpe.narrow
+    override def sufficientType = tpe.narrow
     override def simplify(pv: PatternVar) = this.rebindToObjectCheck()
     override def description = "Obj(%s)".format(fn)
   }
@@ -139,7 +139,9 @@ trait Patterns extends ast.TreeDSL {
 
     private def isColonColon = cleanName == "::"
 
-    override def expandToArity(newArity: Int): List[Pattern] = toPats(args)
+    override def subpatterns(pm: MatchMatrix#PatternMatch) =
+      if (pm.head.isCaseClass) toPats(args)
+      else super.subpatterns(pm)
 
     override def simplify(pv: PatternVar) =
       if (args.isEmpty) this rebindToEmpty tree.tpe
@@ -166,14 +168,13 @@ trait Patterns extends ast.TreeDSL {
     private val MethodType(List(arg, _*), _) = fn.tpe
     private def uaTyped = Typed(tree, TypeTree(arg.tpe)) setType arg.tpe
 
-    // to match an extractor, the arg type must be matched.
-    override def tpe = arg.tpe
+    override def necessaryType = arg.tpe
 
     override def simplify(pv: PatternVar) =
       if (pv.sym.tpe <:< arg.tpe) this
       else this rebindTo uaTyped
 
-    override def description = "UnApp(%s => %s)".format(tpe, resTypesString)
+    override def description = "UnApp(%s => %s)".format(necessaryType, resTypesString)
   }
 
   // 8.1.8 (unapplySeq calls)
@@ -311,20 +312,13 @@ trait Patterns extends ast.TreeDSL {
 
   object UnapplyPattern {
     private object UnapplySeq {
-      /** This is as far as I can tell an elaborate attempt to spot case List(...) and
-       *  avoid the extractor penalty.  It has led to some bugs (e.g. 2800, 3050) which
-       *  I attempt to address below.
-       */
       private object TypeApp {
         def unapply(x: Any) = condOpt(x) {
           case TypeApply(sel @ Select(stor, nme.unapplySeq), List(tpe)) if stor.symbol eq ListModule => tpe
         }
       }
       def unapply(x: UnApply) = condOpt(x) {
-        case UnApply(Apply(TypeApp(tptArg), _), List(ArrayValue(_, xs)))
-          // make sure it's not only _*, as otherwise the rewrite
-          // also removes the instance check.
-          if (xs.isEmpty || xs.size > 1 || !isStar(xs.head))  => (tptArg, xs)
+        case UnApply(Apply(TypeApp(tptArg), _), List(ArrayValue(_, xs))) => (tptArg, xs)
       }
     }
 
@@ -390,7 +384,7 @@ trait Patterns extends ast.TreeDSL {
     protected def mkSingletonFromQualifier = {
       def pType = qualifier match {
         case _: Apply => PseudoType(tree)
-        case _        => singleType(Pattern(qualifier).tpe, sym)
+        case _        => singleType(Pattern(qualifier).necessaryType, sym)
       }
       qualifier.tpe match {
         case t: ThisType  => singleType(t, sym) // this.X
@@ -401,7 +395,7 @@ trait Patterns extends ast.TreeDSL {
 
   sealed trait NamePattern extends Pattern {
     def name: Name
-    override def atomicTpe = tpe.narrow
+    override def sufficientType = tpe.narrow
     override def simplify(pv: PatternVar) = this.rebindToEqualsCheck()
     override def description = name.toString()
   }
@@ -428,31 +422,22 @@ trait Patterns extends ast.TreeDSL {
     protected lazy val Apply(fn, args) = tree
     override def subpatternsForVars: List[Pattern] = toPats(args)
 
+    override def dummies =
+      if (!this.isCaseClass) Nil
+      else emptyPatterns(sufficientType.typeSymbol.caseFieldAccessors.size)
+
     def isConstructorPattern = fn.isType
   }
 
   sealed abstract class Pattern extends PatternBindingLogic {
     val tree: Tree
 
-    // The type of a pattern says: in order for something to match this
-    // pattern, it must conform to this type.  It does NOT say that if
-    // something does conform to this type, it definitely matches the pattern:
-    // see atomic type for that.
-    def tpe = tree.tpe
-
-    // The atomic type of a pattern says: if something matches this, it
-    // definitely matches the pattern (but this is independent of nullness
-    // and guards, which are checked independently.)
-    def atomicTpe = tpe
-
     // returns either a simplification of this pattern or identity.
     def simplify(pv: PatternVar): Pattern = this
-
-    // the arity of this pattern
-    def arity = if (isCaseClass) caseAccessors.length else 0
+    def simplify(): Pattern = this simplify null
 
     // the right number of dummies for this pattern
-    def dummies: List[Pattern] = emptyPatterns(arity)
+    def dummies: List[Pattern] = Nil
 
     // 8.1.13
     // A pattern p is irrefutable for type T if any of the following applies:
@@ -463,26 +448,33 @@ trait Patterns extends ast.TreeDSL {
     //      pi is irrefutable for Ti.
     def irrefutableFor(tpe: Type) = false
 
+    // does this pattern completely cover that pattern (i.e. latter cannot be matched)
+    def completelyCovers(second: Pattern) = false
+
     // Is this a default pattern (untyped "_" or an EmptyTree inserted by the matcher)
     def isDefault = false
 
+    // what type must a scrutinee have to have any chance of matching this pattern?
+    def necessaryType = tpe
+
+    // what type could a scrutinee have which would automatically indicate a match?
+    // (nullness and guards will still be checked.)
+    def sufficientType = tpe
+
     // XXX have to determine if this can be made useful beyond an extractor barrier.
     // Default sufficient type might be NothingClass.tpe, tpe.narrow, ...
 
     // the subpatterns for this pattern (at the moment, that means constructor arguments)
-    def expandToArity(newArity: Int): List[Pattern] =
-      if (isDefault) emptyPatterns(newArity)
-      else if (newArity == 0) Nil
-      else Predef.error("expandToArity(" + newArity + ") in " + this)
+    def subpatterns(pm: MatchMatrix#PatternMatch): List[Pattern] = pm.dummies
 
     def    sym  = tree.symbol
+    def    tpe  = tree.tpe
     def prefix  = tpe.prefix
     def isEmpty = tree.isEmpty
 
     def isSymValid = (sym != null) && (sym != NoSymbol)
     def isModule = sym.isModule || tpe.termSymbol.isModule
     def isCaseClass = tpe.typeSymbol hasFlag Flags.CASE
-    def caseAccessors = tpe.typeSymbol.caseFieldAccessors
     def isObject = isSymValid && prefix.isStable  // XXX not entire logic
 
     def unadorn(t: Tree): Tree = Pattern unadorn t
@@ -524,7 +516,7 @@ trait Patterns extends ast.TreeDSL {
       if (boundVariables.isEmpty) description
       else "%s%s".format(bindingsDescription, description)
     }
-    def toTypeString() = "%s <: x <: %s".format(tpe, atomicTpe)
+    def toTypeString() = "%s <: x <: %s".format(necessaryType, sufficientType)
   }
 
   /*** Extractors ***/
diff --git a/test/files/neg/array-not-seq.check b/test/files/neg/array-not-seq.check
index bd72bb4e13..c16ecdad72 100644
--- a/test/files/neg/array-not-seq.check
+++ b/test/files/neg/array-not-seq.check
@@ -1,16 +1,7 @@
 array-not-seq.scala:2: error: An Array will no longer match as Seq[_].
   def f1(x: Any) = x.isInstanceOf[Seq[_]]
                                  ^
-array-not-seq.scala:4: error: An Array will no longer match as Seq[_].
-    case _: Seq[_]  => true
-          ^
 error: An Array will no longer match as Seq[_].
-array-not-seq.scala:16: error: An Array will no longer match as Seq[_].
-    case (Some(_: Seq[_]), Nil, _)        => 1
-                ^
 error: An Array will no longer match as Seq[_].
-array-not-seq.scala:15: error: An Array will no longer match as Seq[_].
-  def f5(x1: Any, x2: Any, x3: AnyRef) = (x1, x2, x3) match {
-                                              ^
 error: An Array will no longer match as Seq[_].
-7 errors found
+four errors found
diff --git a/test/files/pos/bug3578.scala b/test/files/pos/bug3578.scala
new file mode 100644
index 0000000000..d984118208
--- /dev/null
+++ b/test/files/pos/bug3578.scala
@@ -0,0 +1,30 @@
+object Test {
+  sealed abstract class JValue {
+    def ++(other: JValue) = {
+      def append(value1: JValue, value2: JValue): JValue = (value1, value2) match {
+	case (JNothing, x) => x
+	case (x, JNothing) => x
+	case (JObject(xs), x: JField) => JObject(xs ::: List(x))
+	case (x: JField, JObject(xs)) => JObject(x :: xs)
+	case (JArray(xs), JArray(ys)) => JArray(xs ::: ys)
+	case (JArray(xs), v: JValue) => JArray(xs ::: List(v))
+	case (v: JValue, JArray(xs)) => JArray(v :: xs)
+	case (f1: JField, f2: JField) => JObject(f1 :: f2 :: Nil)
+	case (JField(n, v1), v2: JValue) => JField(n, append(v1, v2))
+	case (x, y) => JArray(x :: y :: Nil)
+      }
+      append(this, other)
+    }
+  }
+
+  case object JNothing extends JValue
+  case object JNull extends JValue
+  case class JString(s: String) extends JValue
+  case class JDouble(num: Double) extends JValue
+  case class JInt(num: BigInt) extends JValue
+  case class JBool(value: Boolean) extends JValue
+  case class JField(name: String, value: JValue) extends JValue
+  case class JObject(obj: List[JField]) extends JValue
+  case class JArray(arr: List[JValue]) extends JValue
+}
+
diff --git a/test/files/run/bug3050.scala b/test/pending/run/bug3050.scala
index aaec99ec14..aaec99ec14 100644
--- a/test/files/run/bug3050.scala
+++ b/test/pending/run/bug3050.scala