Merge pull request scala#650 from adriaanm/topic-virtpatmat

Adriaan Moors · Adriaan Moors · commit 6ed018b2e9ca · 2012-06-03T10:06:59.000-07:00
Unreachability analysis for pattern matches Thanks for reviewing, @retronym!
diff --git a/src/compiler/scala/reflect/internal/settings/MutableSettings.scala b/src/compiler/scala/reflect/internal/settings/MutableSettings.scala
@@ -44,4 +44,5 @@ abstract class MutableSettings extends AbsSettings {
   def maxClassfileName: IntSetting
   def Xexperimental: BooleanSetting
   def XoldPatmat: BooleanSetting
+  def XnoPatmatAnalysis: BooleanSetting
 }
diff --git a/src/compiler/scala/reflect/runtime/Settings.scala b/src/compiler/scala/reflect/runtime/Settings.scala
@@ -35,4 +35,5 @@ class Settings extends internal.settings.MutableSettings {
   val Xexperimental = new BooleanSetting(false)
   val deepCloning = new BooleanSetting (false)
   val XoldPatmat = new BooleanSetting(false)
+  val XnoPatmatAnalysis = new BooleanSetting(false)
 }
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -109,6 +109,7 @@ trait ScalaSettings extends AbsScalaSettings
   val sourceReader  = StringSetting     ("-Xsource-reader", "classname", "Specify a custom method for reading source files.", "")
 
   val XoldPatmat    = BooleanSetting    ("-Xoldpatmat", "Use the pre-2.10 pattern matcher. Otherwise, the 'virtualizing' pattern matcher is used in 2.10.")
+  val XnoPatmatAnalysis = BooleanSetting ("-Xno-patmat-analysis", "Don't perform exhaustivity/unreachability analysis. Also, ignore @switch annotation.")
 
   /** Compatibility stubs for options whose value name did
    *  not previously match the option name.
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
diff --git a/src/compiler/scala/tools/nsc/util/Statistics.scala b/src/compiler/scala/tools/nsc/util/Statistics.scala
@@ -60,6 +60,14 @@ class Statistics extends scala.reflect.internal.util.Statistics {
 
   val macroExpandCount = new Counter
   val macroExpandNanos = new Timer
+
+  val patmatNanos      = new Timer
+  val patmatAnaDPLL    = new Timer
+  val patmatAnaVarEq   = new Timer
+  val patmatCNF        = new Timer
+  val patmatAnaExhaust = new Timer
+  val patmatAnaReach   = new Timer
+  val patmatCNFSizes   = new collection.mutable.HashMap[Int, Int] withDefaultValue 0
 }
 
 object Statistics extends Statistics
@@ -71,7 +79,7 @@ abstract class StatisticsInfo {
   val global: Global
   import global._
 
-  var phasesShown = List("parser", "typer", "erasure", "cleanup")
+  var phasesShown = List("parser", "typer", "patmat", "erasure", "cleanup")
 
   def countNodes(tree: Tree, counts: ClassCounts) {
     for (t <- tree) counts(t.getClass) += 1
@@ -83,10 +91,15 @@ abstract class StatisticsInfo {
   def showRelTyper(timer: Timer) =
     timer+showPercent(timer.nanos, typerNanos.nanos)
 
-  def showCounts(counts: ClassCounts) =
+  def showRelPatmat(timer: Timer) =
+    timer+showPercent(timer.nanos, patmatNanos.nanos)
+
+  def showCounts[T](counts: scala.collection.mutable.Map[T, Int]) =
     counts.toSeq.sortWith(_._2 > _._2).map {
-      case (cls, cnt) =>
+      case (cls: Class[_], cnt) =>
         cls.toString.substring(cls.toString.lastIndexOf("$") + 1)+": "+cnt
+      case (o, cnt) =>
+        o.toString +": "+cnt
     }
 
   def print(phase: Phase) = if (phasesShown contains phase.name) {
@@ -169,6 +182,16 @@ abstract class StatisticsInfo {
       if (timer1   != null) inform("#timer1                  : " + timer1)
       if (timer2   != null) inform("#timer2                  : " + timer2)
       //for (t <- uniques.iterator) println("unique: "+t)
+
+      if (phase.name == "patmat") {
+        inform("time spent in patmat       : " + patmatNanos                   )
+        inform("             of which DPLL : " + showRelPatmat(patmatAnaDPLL   ))
+        inform("of which in CNF conversion : " + showRelPatmat(patmatCNF       ))
+        inform("           CNF size counts : " + showCounts(patmatCNFSizes     ))
+        inform("of which variable equality : " + showRelPatmat(patmatAnaVarEq  ))
+        inform("  of which in exhaustivity : " + showRelPatmat(patmatAnaExhaust))
+        inform("of which in unreachability : " + showRelPatmat(patmatAnaReach  ))
+      }
     }
   }
 }
diff --git a/test/files/neg/patmatexhaust.check b/test/files/neg/patmatexhaust.check
@@ -14,6 +14,9 @@ patmatexhaust.scala:49: error: match may not be exhaustive.
 It would fail on the following inputs: Gp(), Gu
     def ma4(x:Deep) = x match { // missing cases: Gu, Gp
                       ^
+patmatexhaust.scala:55: error: unreachable code
+      case _ if 1 == 0 => 
+                       ^
 patmatexhaust.scala:53: error: match may not be exhaustive.
 It would fail on the following input: Gp()
     def ma5(x:Deep) = x match {
@@ -34,4 +37,4 @@ patmatexhaust.scala:126: error: match may not be exhaustive.
 It would fail on the following input: C1()
     def ma10(x: C) = x match { // not exhaustive: C1 is not abstract.
                      ^
-9 errors found
+10 errors found
diff --git a/test/files/neg/virtpatmat_reach_null.check b/test/files/neg/virtpatmat_reach_null.check
@@ -0,0 +1,4 @@
+virtpatmat_reach_null.scala:13: error: unreachable code
+      case _                              =>  // unreachable
+                                          ^
+one error found
diff --git a/test/files/neg/virtpatmat_reach_null.flags b/test/files/neg/virtpatmat_reach_null.flags
@@ -0,0 +1 @@
+-Xfatal-warnings
diff --git a/test/files/neg/virtpatmat_reach_null.scala b/test/files/neg/virtpatmat_reach_null.scala
@@ -0,0 +1,19 @@
+sealed abstract class Const {
+  final def excludes(other: Const) =
+    (this, other) match {
+      case (_, NullConst)                 =>
+      case (NullConst, _)                 =>
+      case (_: ValueConst, _: ValueConst) =>
+      case (_: ValueConst, _: TypeConst)  =>
+      case (_: TypeConst,  _: ValueConst) =>
+      case (_: TypeConst,  _: TypeConst)  =>
+      case (null, _)                      =>
+      case (_, null)                      =>
+      case null                           =>
+      case _                              =>  // unreachable
+    }
+}
+
+sealed class TypeConst extends Const
+sealed class ValueConst extends Const
+case object NullConst extends Const
diff --git a/test/files/neg/virtpatmat_reach_sealed_unsealed.check b/test/files/neg/virtpatmat_reach_sealed_unsealed.check
@@ -0,0 +1,14 @@
+virtpatmat_reach_sealed_unsealed.scala:16: error: match may not be exhaustive.
+It would fail on the following input: false
+  (true: Boolean) match { case true => } // not exhaustive, but reachable
+       ^
+virtpatmat_reach_sealed_unsealed.scala:18: error: unreachable code
+  (true: Boolean) match { case true => case false =>  case _ => } // exhaustive, last case is unreachable
+                                                             ^
+virtpatmat_reach_sealed_unsealed.scala:19: error: unreachable code
+  (true: Boolean) match { case true => case false =>  case _: Boolean => } // exhaustive, last case is unreachable
+                                                                      ^
+virtpatmat_reach_sealed_unsealed.scala:20: error: unreachable code
+  (true: Boolean) match { case true => case false =>  case _: Any => } // exhaustive, last case is unreachable
+                                                                  ^
+four errors found
diff --git a/test/files/neg/virtpatmat_reach_sealed_unsealed.flags b/test/files/neg/virtpatmat_reach_sealed_unsealed.flags
@@ -0,0 +1 @@
+-Xfatal-warnings
diff --git a/test/files/neg/virtpatmat_reach_sealed_unsealed.scala b/test/files/neg/virtpatmat_reach_sealed_unsealed.scala
@@ -0,0 +1,21 @@
+sealed abstract class X
+sealed case class A(x: Int) extends X
+
+// test reachability on mixed sealed / non-sealed matches
+object Test extends App {
+  val B: X = A(0)
+  val C: X = A(1)
+
+  // all cases are reachable and the match is exhaustive
+  (C: X) match {
+    case B =>
+    case C =>
+    case A(_) =>
+  }
+
+  (true: Boolean) match { case true => } // not exhaustive, but reachable
+  (true: Boolean) match { case true => case false => } // exhaustive, reachable
+  (true: Boolean) match { case true => case false =>  case _ => } // exhaustive, last case is unreachable
+  (true: Boolean) match { case true => case false =>  case _: Boolean => } // exhaustive, last case is unreachable
+  (true: Boolean) match { case true => case false =>  case _: Any => } // exhaustive, last case is unreachable
+}
diff --git a/test/files/pos/virtpatmat_reach_const.scala b/test/files/pos/virtpatmat_reach_const.scala
@@ -0,0 +1,11 @@
+// check the interaction between constants and type tests in creating the equality axioms
+object Test {
+  type Formula = List[String]
+  val TrueF: Formula = List()
+  def distribute(a: Formula, b: Formula) = (a, b) match {
+    case (TrueF, _) =>
+    case (_, TrueF) =>  // bug: considered unreachable
+    case (a :: Nil, b :: Nil) =>
+    case _ =>
+  }
+}

Original file line number	Diff line number	Diff line change
`@@ -44,4 +44,5 @@ abstract class MutableSettings extends AbsSettings {`
`44`	`44`	`def maxClassfileName: IntSetting`
`45`	`45`	`def Xexperimental: BooleanSetting`
`46`	`46`	`def XoldPatmat: BooleanSetting`
	`47`	`+ def XnoPatmatAnalysis: BooleanSetting`
`47`	`48`	`}`
Original file line number	Diff line number	Diff line change
`@@ -35,4 +35,5 @@ class Settings extends internal.settings.MutableSettings {`
`35`	`35`	`val Xexperimental = new BooleanSetting(false)`
`36`	`36`	`val deepCloning = new BooleanSetting (false)`
`37`	`37`	`val XoldPatmat = new BooleanSetting(false)`
	`38`	`+ val XnoPatmatAnalysis = new BooleanSetting(false)`
`38`	`39`	`}`