SI-5739 store sub-patterns in local vals

Also closes SI-5158 (debuggability), SI-6070 (soundness).

To improve both debuggability and soundness,
we now store the result of an extractor (user-defined and synthetic)
in local variables.

For the case class case, this also fixes the soundness bug SI-6070,
as this prevents post-match mutation of bound variables.

The core of the refactoring consisted of introducing the PreserveSubPatBinders
trait, which introduces local variables instead of substituting symbols
for the RHS of those variables (so this can be seen as reverting the premature optimization
of inline the case-class getters into the case body).

Since TreeMakerToCond fuses the substitutions performed in a match to find out
which symbolic values binders evaluate to, masquerade PreserveSubPatBinders's
binding of subPatBinders and subPatRefs as the corresponding substitution.

Consider `case class Foo(bar: Int)`, then `case y@Foo(x) => println(x)`
gives rise to `{val x = y.bar; println(x)}` (instead of `println(y.bar)`),
and `subPatternsAsSubstitution` pretends we still replace `x` by `y.bar`,
instead of storing it in a local variable so that the rest of the analysis need not be modified.

Misc notes:
- correct type for seq-subpattern
- more error resilience (ill-typed patterns sometimes slip past the typechecker -- reopened SI-4425)

TODO: come up with a more abstract framework for expressing bound symbols and their values

7 files changed, 168 insertions, 53 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
index 4e4176e531..afe143553c 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
@@ -15,6 +15,7 @@ import scala.tools.nsc.transform.Transform
 import scala.collection.mutable.HashSet
 import scala.collection.mutable.HashMap
 import reflect.internal.util.Statistics
+import scala.reflect.internal.Types
 
 /** Translate pattern matching.
   *
@@ -71,7 +72,15 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       case Match(sel, cases) =>
         val origTp = tree.tpe
         // setType origTp intended for CPS -- TODO: is it necessary?
-        localTyper.typed(translator.translateMatch(treeCopy.Match(tree, transform(sel), transformTrees(cases).asInstanceOf[List[CaseDef]]))) setType origTp
+        val translated = translator.translateMatch(treeCopy.Match(tree, transform(sel), transformTrees(cases).asInstanceOf[List[CaseDef]]))
+        try {
+          localTyper.typed(translated) setType origTp
+        } catch {
+          case x: (Types#TypeError) =>
+            // TODO: this should never happen; error should've been reported during type checking
+            unit.error(tree.pos, "error during expansion of this match (this is a scalac bug).\nThe underlying error was: "+ x.msg)
+            translated
+        }
       case Try(block, catches, finalizer) =>
         treeCopy.Try(tree, transform(block), translator.translateTry(transformTrees(catches).asInstanceOf[List[CaseDef]], tree.tpe, tree.pos), transform(finalizer))
       case _ => super.transform(tree)
@@ -547,7 +556,10 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         if(isSeq) {
           val TypeRef(pre, SeqClass, args) = seqTp
           // do repeated-parameter expansion to match up with the expected number of arguments (in casu, subpatterns)
-          formalTypes(rawSubPatTypes.init :+ typeRef(pre, RepeatedParamClass, args), nbSubPats)
+          val formalsWithRepeated = rawSubPatTypes.init :+ typeRef(pre, RepeatedParamClass, args)
+
+          if (lastIsStar) formalTypes(formalsWithRepeated, nbSubPats - 1) :+ seqTp
+          else formalTypes(formalsWithRepeated, nbSubPats)
         } else rawSubPatTypes
 
       protected def rawSubPatTypes: List[Type]
@@ -637,7 +649,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       // binder has type paramType
       def treeMaker(binder: Symbol, pos: Position): TreeMaker = {
         // checks binder ne null before chaining to the next extractor
-        ProductExtractorTreeMaker(binder, lengthGuard(binder))(Substitution(subPatBinders, subPatRefs(binder)))
+        ProductExtractorTreeMaker(binder, lengthGuard(binder))(subPatBinders, subPatRefs(binder))
       }
 
       // reference the (i-1)th case accessor if it exists, otherwise the (i-1)th tuple component
@@ -681,7 +693,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         // the extractor call (applied to the binder bound by the flatMap corresponding to the previous (i.e., enclosing/outer) pattern)
         val extractorApply = atPos(pos)(spliceApply(patBinderOrCasted))
         val binder         = freshSym(pos, pureType(resultInMonad)) // can't simplify this when subPatBinders.isEmpty, since UnitClass.tpe is definitely wrong when isSeq, and resultInMonad should always be correct since it comes directly from the extractor's result type
-        ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder)(Substitution(subPatBinders, subPatRefs(binder)), resultType.typeSymbol == BooleanClass, checkedLength, patBinderOrCasted)
+        ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder)(subPatBinders, subPatRefs(binder), resultType.typeSymbol == BooleanClass, checkedLength, patBinderOrCasted)
       }
 
       override protected def seqTree(binder: Symbol): Tree =
@@ -837,6 +849,20 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       }
       private[this] var currSub: Substitution = null
 
+      /** The substitution that specifies the trees that compute the values of the subpattern binders.
+       *
+       * Should not be used to perform actual substitution!
+       * Only used to reason symbolically about the values the subpattern binders are bound to.
+       * See TreeMakerToCond#updateSubstitution.
+       *
+       * Overridden in PreserveSubPatBinders to pretend it replaces the subpattern binders by subpattern refs
+       * (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.)
+       *
+       * TODO: clean this up, would be nicer to have some higher-level way to compute
+       * the binders bound by this tree maker and the symbolic values that correspond to them
+       */
+      def subPatternsAsSubstitution: Substitution = substitution
+
       // build Tree that chains `next` after the current extractor
       def chainBefore(next: Tree)(casegen: Casegen): Tree
     }
@@ -885,6 +911,23 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         atPos(pos)(casegen.flatMapCond(cond, res, nextBinder, substitution(next)))
     }
 
+    trait PreserveSubPatBinders extends NoNewBinders {
+      val subPatBinders: List[Symbol]
+      val subPatRefs: List[Tree]
+
+      /** The substitution that specifies the trees that compute the values of the subpattern binders.
+       *
+       * We pretend to replace the subpattern binders by subpattern refs
+       * (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.)
+       */
+      override def subPatternsAsSubstitution =
+        Substitution(subPatBinders, subPatRefs) >> super.subPatternsAsSubstitution
+
+      import CODE._
+      def bindSubPats(in: Tree): Tree =
+        Block((subPatBinders, subPatRefs).zipped.map { case (sym, ref) => VAL(sym) === ref }, in)
+    }
+
     /**
      * Make a TreeMaker that will result in an extractor call specified by `extractor`
      * the next TreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing
@@ -892,12 +935,23 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
      * the function's body is determined by the next TreeMaker
      * in this function's body, and all the subsequent ones, references to the symbols in `from` will be replaced by the corresponding tree in `to`
      */
-    case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol)(val localSubstitution: Substitution, extractorReturnsBoolean: Boolean, val checkedLength: Option[Int], val prevBinder: Symbol) extends FunTreeMaker {
+    case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol)(
+          val subPatBinders: List[Symbol],
+          val subPatRefs: List[Tree],
+          extractorReturnsBoolean: Boolean,
+          val checkedLength: Option[Int],
+          val prevBinder: Symbol) extends FunTreeMaker with PreserveSubPatBinders {
+
       def chainBefore(next: Tree)(casegen: Casegen): Tree = {
-        val condAndNext = extraCond map (casegen.ifThenElseZero(_, next)) getOrElse next
+        val condAndNext = extraCond match {
+          case Some(cond) =>
+            casegen.ifThenElseZero(substitution(cond), bindSubPats(substitution(next)))
+          case _ =>
+            bindSubPats(substitution(next))
+        }
         atPos(extractor.pos)(
-          if (extractorReturnsBoolean) casegen.flatMapCond(extractor, CODE.UNIT, nextBinder, substitution(condAndNext))
-          else casegen.flatMap(extractor, nextBinder, substitution(condAndNext))
+          if (extractorReturnsBoolean) casegen.flatMapCond(extractor, CODE.UNIT, nextBinder, condAndNext)
+          else casegen.flatMap(extractor, nextBinder, condAndNext)
         )
       }
 
@@ -905,12 +959,17 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
     }
 
     // TODO: allow user-defined unapplyProduct
-    case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree])(val localSubstitution: Substitution) extends FunTreeMaker { import CODE._
+    case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree])(
+          val subPatBinders: List[Symbol],
+          val subPatRefs: List[Tree]) extends FunTreeMaker with PreserveSubPatBinders {
+
+      import CODE._
       val nextBinder = prevBinder // just passing through
+
       def chainBefore(next: Tree)(casegen: Casegen): Tree = {
         val nullCheck = REF(prevBinder) OBJ_NE NULL
         val cond = extraCond map (nullCheck AND _) getOrElse nullCheck
-        casegen.ifThenElseZero(cond, substitution(next))
+        casegen.ifThenElseZero(cond, bindSubPats(substitution(next)))
       }
 
       override def toString = "P"+(prevBinder.name,  extraCond getOrElse "", localSubstitution)
@@ -1541,7 +1600,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
          * TODO: don't ignore outer-checks
          */
         def apply(tm: TreeMaker): Cond = {
-          if (!substitutionComputed) updateSubstitution(tm.substitution)
+          if (!substitutionComputed) updateSubstitution(tm.subPatternsAsSubstitution)
 
           tm match {
             case ttm@TypeTestTreeMaker(prevBinder, testedBinder, pt, _)   =>
diff --git a/test/files/neg/t4425.check b/test/files/neg/t4425.check
index 0f2fe6f2d1..a6a1a1fad4 100644
--- a/test/files/neg/t4425.check
+++ b/test/files/neg/t4425.check
@@ -1,4 +1,5 @@
-t4425.scala:3: error: isInstanceOf cannot test if value types are references.
+t4425.scala:3: error: error during expansion of this match (this is a scalac bug).
+The underlying error was: value _1 is not a member of object Foo.X
   42 match { case _ X _ => () }
-                    ^
+     ^
 one error found
diff --git a/test/files/run/inline-ex-handlers.check b/test/files/run/inline-ex-handlers.check
index 7d96c447b0..25e1b2a4dd 100644
--- a/test/files/run/inline-ex-handlers.check
+++ b/test/files/run/inline-ex-handlers.check
@@ -34,11 +34,11 @@
 <     101	JUMP 4
 <     
 <   4: 
-512c517
+515c520
 <   blocks: [1,2,3,4,6,7,8,9,10]
 ---
 >   blocks: [1,2,3,4,6,7,8,9,10,11,12,13]
-541c546,551
+544c549,554
 <     306	THROW(MyException)
 ---
 >     ?	JUMP 11
@@ -47,7 +47,7 @@
 >     ?	LOAD_LOCAL(variable monitor4)
 >     305	MONITOR_EXIT
 >     ?	JUMP 12
-547c557,563
+550c560,566
 <     ?	THROW(Throwable)
 ---
 >     ?	JUMP 12
@@ -57,7 +57,7 @@
 >     304	MONITOR_EXIT
 >     ?	STORE_LOCAL(value t)
 >     ?	JUMP 13
-553c569,582
+556c572,585
 <     ?	THROW(Throwable)
 ---
 >     ?	STORE_LOCAL(value t)
@@ -74,19 +74,19 @@
 >     310	CALL_PRIMITIVE(EndConcat)
 >     310	CALL_METHOD scala.Predef.println (dynamic)
 >     310	JUMP 2
-577c606
+580c609
 <     catch (Throwable) in ArrayBuffer(7, 8, 9, 10) starting at: 6
 ---
 >     catch (Throwable) in ArrayBuffer(7, 8, 9, 10, 11) starting at: 6
-580c609
+583c612
 <     catch (Throwable) in ArrayBuffer(4, 6, 7, 8, 9, 10) starting at: 3
 ---
 >     catch (Throwable) in ArrayBuffer(4, 6, 7, 8, 9, 10, 11, 12) starting at: 3
-612c641
+615c644
 <   blocks: [1,2,3,4,5,6,7,9,10]
 ---
 >   blocks: [1,2,3,4,5,6,7,9,10,11,12]
-636c665,671
+639c668,674
 <     78	THROW(IllegalArgumentException)
 ---
 >     ?	STORE_LOCAL(value e)
@@ -96,7 +96,7 @@
 >     81	LOAD_LOCAL(value e)
 >     ?	STORE_LOCAL(variable exc1)
 >     ?	JUMP 12
-665c700,714
+668c703,717
 <     81	THROW(Exception)
 ---
 >     ?	STORE_LOCAL(variable exc1)
@@ -114,15 +114,15 @@
 >     84	STORE_LOCAL(variable result)
 >     84	LOAD_LOCAL(variable exc1)
 >     84	THROW(Throwable)
-687c736
+690c739
 <     catch (<none>) in ArrayBuffer(4, 6, 7, 9) starting at: 3
 ---
 >     catch (<none>) in ArrayBuffer(4, 6, 7, 9, 11) starting at: 3
-713c762
+716c765
 <   blocks: [1,2,3,4,5,6,9,12,14,17,18,19,22,25,27,28,30,31]
 ---
 >   blocks: [1,2,3,4,5,6,9,12,14,17,18,19,22,25,27,28,30,31,32,33,34]
-737c786,793
+740c789,796
 <     172	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value ex6)
@@ -133,12 +133,12 @@
 >     170	STORE_LOCAL(value x4)
 >     170	SCOPE_ENTER value x4
 >     170	JUMP 18
-793c849,850
+798c854,855
 <     177	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value ex6)
 >     ?	JUMP 33
-797c854,861
+802c859,866
 <     170	THROW(Throwable)
 ---
 >     ?	STORE_LOCAL(value ex6)
@@ -149,17 +149,17 @@
 >     169	STORE_LOCAL(value x4)
 >     169	SCOPE_ENTER value x4
 >     169	JUMP 5
-830c894,895
+837c901,902
 <     182	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(variable exc2)
 >     ?	JUMP 34
-834c899,900
+841c906,907
 <     169	THROW(Throwable)
 ---
 >     ?	STORE_LOCAL(variable exc2)
 >     ?	JUMP 34
-835a902,914
+842a909,921
 >   34: 
 >     184	LOAD_MODULE object Predef
 >     184	CONSTANT("finally")
@@ -173,19 +173,19 @@
 >     185	LOAD_LOCAL(variable exc2)
 >     185	THROW(Throwable)
 >     
-856c935
+863c942
 <     catch (Throwable) in ArrayBuffer(17, 18, 19, 22, 25, 27, 28, 30) starting at: 4
 ---
 >     catch (Throwable) in ArrayBuffer(17, 18, 19, 22, 25, 27, 28, 30, 32) starting at: 4
-859c938
+866c945
 <     catch (<none>) in ArrayBuffer(4, 5, 6, 9, 12, 17, 18, 19, 22, 25, 27, 28, 30) starting at: 3
 ---
 >     catch (<none>) in ArrayBuffer(4, 5, 6, 9, 12, 17, 18, 19, 22, 25, 27, 28, 30, 32, 33) starting at: 3
-885c964
+892c971
 <   blocks: [1,2,3,6,7,8,11,14,16,17,19]
 ---
 >   blocks: [1,2,3,6,7,8,11,14,16,17,19,20]
-909c988,995
+916c995,1002
 <     124	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value ex6)
@@ -196,15 +196,15 @@
 >     122	STORE_LOCAL(value x4)
 >     122	SCOPE_ENTER value x4
 >     122	JUMP 7
-969c1055
+979c1065
 <     catch (IllegalArgumentException) in ArrayBuffer(6, 7, 8, 11, 14, 16, 17, 19) starting at: 3
 ---
 >     catch (IllegalArgumentException) in ArrayBuffer(6, 7, 8, 11, 14, 16, 17, 19, 20) starting at: 3
-995c1081
+1005c1091
 <   blocks: [1,2,3,4,5,8,11,15,16,17,19]
 ---
 >   blocks: [1,2,3,5,8,11,15,16,17,19,20]
-1019c1105,1114
+1029c1115,1124
 <     148	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value ex6)
@@ -217,15 +217,15 @@
 >     154	LOAD_LOCAL(value x4)
 >     154	IS_INSTANCE REF(class MyException)
 >     154	CZJUMP (BOOL)NE ? 5 : 11
-1040,1042d1134
+1050,1052d1144
 <     145	JUMP 4
 <     
 <   4: 
-1275c1367
+1288c1380
 <   blocks: [1,2,3,4,5,7]
 ---
 >   blocks: [1,2,3,4,5,7,8]
-1299c1391,1398
+1312c1404,1411
 <     38	THROW(IllegalArgumentException)
 ---
 >     ?	STORE_LOCAL(value e)
@@ -236,16 +236,16 @@
 >     42	CONSTANT("IllegalArgumentException")
 >     42	CALL_METHOD scala.Predef.println (dynamic)
 >     42	JUMP 2
-1348c1447
+1361c1460
 <   blocks: [1,2,3,4,5,8,11,13,14,16,17,19]
 ---
 >   blocks: [1,2,3,5,8,11,13,14,16,17,19,20]
-1372c1471,1472
+1385c1484,1485
 <     203	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value ex6)
 >     ?	JUMP 20
-1392c1492,1501
+1405c1505,1514
 <     209	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value ex6)
@@ -258,15 +258,15 @@
 >     212	LOAD_LOCAL(value x4)
 >     212	IS_INSTANCE REF(class MyException)
 >     212	CZJUMP (BOOL)NE ? 5 : 11
-1405,1407d1513
+1418,1420d1526
 <     200	JUMP 4
 <     
 <   4: 
-1467c1573
+1483c1589
 <   blocks: [1,2,3,4,5,7]
 ---
 >   blocks: [1,2,3,4,5,7,8]
-1491c1597,1604
+1507c1613,1620
 <     58	THROW(IllegalArgumentException)
 ---
 >     ?	STORE_LOCAL(value e)
@@ -277,11 +277,11 @@
 >     62	CONSTANT("RuntimeException")
 >     62	CALL_METHOD scala.Predef.println (dynamic)
 >     62	JUMP 2
-1540c1653
+1556c1669
 <   blocks: [1,2,3,4]
 ---
 >   blocks: [1,2,3,4,5]
-1560c1673,1678
+1576c1689,1694
 <     229	THROW(MyException)
 ---
 >     ?	JUMP 5
@@ -290,19 +290,19 @@
 >     ?	LOAD_LOCAL(variable monitor1)
 >     228	MONITOR_EXIT
 >     228	THROW(Throwable)
-1566c1684
+1582c1700
 <     ?	THROW(Throwable)
 ---
 >     228	THROW(Throwable)
-1594c1712
+1610c1728
 <   locals: value args, variable result, variable monitor2, variable monitorResult1
 ---
 >   locals: value exception$1, value args, variable result, variable monitor2, variable monitorResult1
-1596c1714
+1612c1730
 <   blocks: [1,2,3,4]
 ---
 >   blocks: [1,2,3,4,5]
-1619c1737,1745
+1635c1753,1761
 <     245	THROW(MyException)
 ---
 >     ?	STORE_LOCAL(value exception$1)
@@ -314,7 +314,7 @@
 >     ?	LOAD_LOCAL(variable monitor2)
 >     244	MONITOR_EXIT
 >     244	THROW(Throwable)
-1625c1751
+1641c1767
 <     ?	THROW(Throwable)
 ---
 >     244	THROW(Throwable)
diff --git a/test/files/run/t5158.check b/test/files/run/t5158.check
new file mode 100644
index 0000000000..573541ac97
--- /dev/null
+++ b/test/files/run/t5158.check
@@ -0,0 +1 @@
+0
diff --git a/test/files/run/t5158.scala b/test/files/run/t5158.scala
new file mode 100644
index 0000000000..3028ffa9e0
--- /dev/null
+++ b/test/files/run/t5158.scala
@@ -0,0 +1,17 @@
+case class B(var x: Int) {
+  def succ() {
+    x = x + 1
+  }
+}
+
+object Test {
+  def main(args: Array[String]) {
+    val b = B(0)
+    b match {
+      case B(x) =>
+        //println(x)
+        b.succ()
+        println(x)
+    }
+  }
+}
\ No newline at end of file
diff --git a/test/files/run/t6070.check b/test/files/run/t6070.check
new file mode 100644
index 0000000000..00750edc07
--- /dev/null
+++ b/test/files/run/t6070.check
@@ -0,0 +1 @@
+3
diff --git a/test/files/run/t6070.scala b/test/files/run/t6070.scala
new file mode 100644
index 0000000000..b6af48ef21
--- /dev/null
+++ b/test/files/run/t6070.scala
@@ -0,0 +1,36 @@
+abstract class Bomb {
+  type T
+  val x: T
+
+  def size(that: T): Int
+}
+
+class StringBomb extends Bomb {
+  type T = String
+  val x = "abc"
+  def size(that: String): Int = that.length
+}
+
+class IntBomb extends Bomb { 
+  type T = Int
+  val x = 10
+
+  def size(that: Int) = x + that
+}
+
+case class Mean(var bomb: Bomb)
+
+object Test extends App {
+  def foo(x: Mean) = x match {
+    case Mean(b) => 
+      // BUG: b is assumed to be a stable identifier, but it can actually be mutated
+      println(b.size({ mutate(); b.x }))
+  }
+
+  def mutate() {
+    m.bomb = new IntBomb
+  }
+
+  val m = Mean(new StringBomb)
+  foo(m) // should print 3
+}
\ No newline at end of file