SI-7669 Fix exhaustivity warnings for recursive ADTs.

The pattern matcher's analysis was correctly finding
models under which the match in the enclosed test
could fail. But, when trying to render that model
as a counter example, it ran into an internal inconsistency
and gave up.

That inconsistency arose from VariableAssignment, which:

> turn the variable assignments into a tree
> the root is the scrutinee (x1), edges are labelled
> by the fields that are assigned a node is a variable
> example (which is later turned into a counter example)

In the process, it notes the unreachable case `V2 = NotHandled`,
which can only arise if `V1 = Op`, ie the scrutinee is `Op(NotHandled())`.
V2 is assosicated with the path `x1.arg`. The code then looked for
any variable assosicated with the prefix `x1` and registered that its
field `arg` was assosicated with this variable assignment.

However, the assignment for `V1 = NotHandled` (another missing case)
is also associated with the path `x1`. Registering this field makes
no sense here; we should only do that for `Op`.

This commit conditionally registers the fields based on the class
of `VariableAssignment#cls`. We no longer hit the inconsistency in
`VariableAssignment#allFieldAssignmentsLegal`.

This favourably changes the results of two existing tests.

I had to tweak the counter example pruning to avoid relying on
CounterExample.==, which is flaky in the light of Nil and List().
It is possible to have:

     A, B where A != B && A.coveredBy(B) && B.coveredBy(A)

Luckily it is straightforward to implement pruning entirely with
coveredBy.

7 files changed, 40 insertions, 7 deletions

diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala
index f527c30b8a..f089c8f5a5 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala
@@ -488,8 +488,13 @@ trait MatchAnalysis extends MatchApproximation {
 
     object CounterExample {
       def prune(examples: List[CounterExample]): List[CounterExample] = {
-        val distinct = examples.filterNot(_ == NoExample).toSet
-        distinct.filterNot(ce => distinct.exists(other => (ce ne other) && ce.coveredBy(other))).toList
+        // SI-7669 Warning: we don't used examples.distinct here any more as
+        //         we can have A != B && A.coveredBy(B) && B.coveredBy(A)
+        //         with Nil and List().
+        val result = mutable.Buffer[CounterExample]()
+        for (example <- examples if (!result.exists(example coveredBy _)))
+          result += example
+        result.toList
       }
     }
 
@@ -591,7 +596,7 @@ trait MatchAnalysis extends MatchApproximation {
         private def unique(variable: Var): VariableAssignment =
           uniques.getOrElseUpdate(variable, {
             val (eqTo, neqTo) = varAssignment.getOrElse(variable, (Nil, Nil)) // TODO
-            VariableAssignment(variable, eqTo.toList, neqTo.toList, mutable.HashMap.empty)
+            VariableAssignment(variable, eqTo.toList, neqTo.toList)
           })
 
         def apply(variable: Var): VariableAssignment = {
@@ -605,7 +610,7 @@ trait MatchAnalysis extends MatchApproximation {
           else {
             findVar(pre) foreach { preVar =>
               val outerCtor = this(preVar)
-              outerCtor.fields(field) = newCtor
+              outerCtor.addField(field, newCtor)
             }
             newCtor
           }
@@ -613,7 +618,8 @@ trait MatchAnalysis extends MatchApproximation {
       }
 
       // node in the tree that describes how to construct a counter-example
-      case class VariableAssignment(variable: Var, equalTo: List[Const], notEqualTo: List[Const], fields: scala.collection.mutable.Map[Symbol, VariableAssignment]) {
+      case class VariableAssignment(variable: Var, equalTo: List[Const], notEqualTo: List[Const]) {
+        private val fields: mutable.Map[Symbol, VariableAssignment] = mutable.HashMap.empty
         // need to prune since the model now incorporates all super types of a constant (needed for reachability)
         private lazy val uniqueEqualTo = equalTo filterNot (subsumed => equalTo.exists(better => (better ne subsumed) && instanceOfTpImplies(better.tp, subsumed.tp)))
         private lazy val prunedEqualTo = uniqueEqualTo filterNot (subsumed => variable.staticTpCheckable <:< subsumed.tp)
@@ -622,6 +628,11 @@ trait MatchAnalysis extends MatchApproximation {
         private lazy val cls        = if (ctor == NoSymbol) NoSymbol else ctor.owner
         private lazy val caseFieldAccs = if (cls == NoSymbol) Nil else cls.caseFieldAccessors
 
+        def addField(symbol: Symbol, assign: VariableAssignment) {
+          // SI-7669 Only register this field if if this class contains it.
+          val shouldConstrainField = !symbol.isCaseAccessor || caseFieldAccs.contains(symbol)
+          if (shouldConstrainField) fields(symbol) = assign
+        }
 
         def allFieldAssignmentsLegal: Boolean =
           (fields.keySet subsetOf caseFieldAccs.toSet) && fields.values.forall(_.allFieldAssignmentsLegal)
diff --git a/test/files/neg/exhausting.check b/test/files/neg/exhausting.check
index c573eb3e15..619849693c 100644
--- a/test/files/neg/exhausting.check
+++ b/test/files/neg/exhausting.check
@@ -1,5 +1,5 @@
 exhausting.scala:21: warning: match may not be exhaustive.
-It would fail on the following input: List(_, _, _)
+It would fail on the following inputs: List(_), List(_, _, _)
   def fail1[T](xs: List[T]) = xs match {
                               ^
 exhausting.scala:27: warning: match may not be exhaustive.
diff --git a/test/files/neg/exhausting.scala b/test/files/neg/exhausting.scala
index 5554ee2671..01c34f7039 100644
--- a/test/files/neg/exhausting.scala
+++ b/test/files/neg/exhausting.scala
@@ -17,7 +17,7 @@ object Test {
     case (_: Foo[_], _: Foo[_]) => ()
   }
 
-  // fails for: ::(_, ::(_, ::(_, _)))
+  // fails for: ::(_, Nil), ::(_, ::(_, ::(_, _))), ...
   def fail1[T](xs: List[T]) = xs match {
     case Nil            => "ok"
     case x :: y :: Nil  => "ok"
diff --git a/test/files/neg/t7669.check b/test/files/neg/t7669.check
new file mode 100644
index 0000000000..c090ed18ce
--- /dev/null
+++ b/test/files/neg/t7669.check
@@ -0,0 +1,7 @@
+t7669.scala:9: warning: match may not be exhaustive.
+It would fail on the following input: NotHandled(_)
+  def exhausto(expr: Expr): Unit = expr match {
+                                   ^
+error: No warnings can be incurred under -Xfatal-warnings.
+one warning found
+one error found
diff --git a/test/files/neg/t7669.flags b/test/files/neg/t7669.flags
new file mode 100644
index 0000000000..85d8eb2ba2
--- /dev/null
+++ b/test/files/neg/t7669.flags
@@ -0,0 +1 @@
+-Xfatal-warnings
diff --git a/test/files/neg/t7669.scala b/test/files/neg/t7669.scala
new file mode 100644
index 0000000000..12441ec056
--- /dev/null
+++ b/test/files/neg/t7669.scala
@@ -0,0 +1,13 @@
+object Test {
+
+  sealed abstract class Expr
+  // Change type of `arg` to `Any` and the exhaustiveness warning
+  // is issued below
+  case class Op(arg: Expr) extends Expr
+  case class NotHandled(num: Double) extends Expr
+
+  def exhausto(expr: Expr): Unit = expr match {
+    case Op(Op(_)) =>
+    case Op(_) =>
+  }
+}
diff --git a/test/files/run/virtpatmat_casting.scala b/test/files/run/virtpatmat_casting.scala
index d970abae90..22ac29bc3b 100644
--- a/test/files/run/virtpatmat_casting.scala
+++ b/test/files/run/virtpatmat_casting.scala
@@ -4,5 +4,6 @@ object Test extends App {
 // since the :: extractor's argument must be a ::, there has to be a cast before its unapply is invoked    
     case x :: y :: z :: a :: xs => xs ++ List(x)
     case x :: y :: z :: xs => xs ++ List(x)
+    case _ => List(0)
   })
 }