Reworked exhaustiveness checking yet further, a...

Reworked exhaustiveness checking yet further, and moved it and some
other pieces into their own file.

4 files changed, 145 insertions, 117 deletions

diff --git a/src/compiler/scala/tools/nsc/matching/Matrix.scala b/src/compiler/scala/tools/nsc/matching/Matrix.scala
index f5bad3ed22..07923059c1 100644
--- a/src/compiler/scala/tools/nsc/matching/Matrix.scala
+++ b/src/compiler/scala/tools/nsc/matching/Matrix.scala
@@ -8,8 +8,9 @@ package matching
 
 import transform.ExplicitOuter
 import util.Position
+import symtab.Flags
 
-trait Matrix extends PatternOptimizer {
+trait Matrix extends MatrixAdditions {
   self: ExplicitOuter with ParallelMatching =>
 
   import global.{ typer => _, _ }
diff --git a/src/compiler/scala/tools/nsc/matching/PatternOptimizer.scala b/src/compiler/scala/tools/nsc/matching/MatrixAdditions.scala
index aa51ea4bd3..c1364af806 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternOptimizer.scala
+++ b/src/compiler/scala/tools/nsc/matching/MatrixAdditions.scala
@@ -8,14 +8,20 @@ package matching
 
 import transform.ExplicitOuter
 
-trait PatternOptimizer extends ast.TreeDSL
+/** Traits which are mixed into MatchMatrix, but separated out as
+ *  (somewhat) independent components to keep them on the sidelines.
+ */
+trait MatrixAdditions extends ast.TreeDSL
 {
   self: ExplicitOuter with ParallelMatching =>
 
   import global.{ typer => _, _ }
   import symtab.Flags
   import CODE._
+  import Debug._
 
+  /** The Squeezer, responsible for all the squeezing.
+   */
   private[matching] trait Squeezer {
     self: MatrixContext =>
 
@@ -78,6 +84,8 @@ trait PatternOptimizer extends ast.TreeDSL
     }
   }
 
+  /** The Optimizer, responsible for some of the optimizing.
+   */
   private[matching] trait MatchMatrixOptimizer {
     self: MatchMatrix =>
 
@@ -134,4 +142,98 @@ trait PatternOptimizer extends ast.TreeDSL
       returning[Tree](resetTraverser traverse _)(lxtt transform tree)
     }
   }
+
+  /** The Exhauster.
+   */
+  private[matching] trait MatrixExhaustiveness {
+    self: MatchMatrix =>
+
+    import self.context._
+
+    /** Exhaustiveness checking requires looking for sealed classes
+     *  and if found, making sure all children are covered by a pattern.
+     */
+    class ExhaustivenessChecker(rep: Rep) {
+      val Rep(tvars, rows) = rep
+
+      import Flags.{ MUTABLE, ABSTRACT, SEALED, TRANS_FLAG }
+
+      private case class Combo(index: Int, sym: Symbol) {
+        // is this combination covered by the given pattern?
+        def isCovered(p: Pattern) = {
+          def cmpSymbols(t1: Type, t2: Type)  = t1.typeSymbol eq t2.typeSymbol
+          def coversSym = {
+            val tpe = decodedEqualsType(p.tpe)
+            lazy val lmoc = sym.linkedModuleOfClass
+            val symtpe =
+              if ((sym hasFlag Flags.MODULE) && (lmoc ne NoSymbol))
+                singleType(sym.tpe.prefix, lmoc)   // e.g. None, Nil
+              else sym.tpe
+
+            (tpe.typeSymbol == sym) ||
+            (symtpe <:< tpe) ||
+            (symtpe.parents exists (x => cmpSymbols(x, tpe))) || // e.g. Some[Int] <: Option[&b]
+            ((tpe.prefix memberType sym) <:< tpe)  // outer, see combinator.lexical.Scanner
+          }
+
+          cond(p.tree) {
+            case _: UnApply | _: ArrayValue => true
+            case x                          => p.isDefault || coversSym
+          }
+        }
+      }
+
+      /* True if the patterns in 'row' cover the given type symbol combination, and has no guard. */
+      private def rowCoversCombo(row: Row, combos: List[Combo]) =
+        row.guard.isEmpty && (combos forall (c => c isCovered row.pats(c.index)))
+
+      private def requiresExhaustive(s: Symbol) =
+         (s hasFlag MUTABLE) &&                 // indicates that have not yet checked exhaustivity
+        !(s hasFlag TRANS_FLAG) &&              // indicates @unchecked
+         (s.tpe.typeSymbol hasFlag SEALED) &&
+         { s resetFlag MUTABLE ; true }         // side effects MUTABLE flag
+
+      private def sealedSymsFor(s: Symbol): Set[Symbol] = {
+        def countSealed(child: Symbol) = {
+          // include base class only if non-abstract
+          def baseSet = if (child hasFlag ABSTRACT) Set() else Set(child)
+          sealedSymsFor(child) ++ baseSet
+        }
+        if (s hasFlag SEALED) s.children flatMap countSealed
+        else Set()
+      }
+      private lazy val inexhaustives: List[List[Combo]] = {
+        val collected =
+          for ((sym, i) <- tvars.zipWithIndex ; if requiresExhaustive(sym)) yield
+            i -> sealedSymsFor(sym.tpe.typeSymbol)
+
+        val folded =
+          collected.foldRight(List[List[Combo]]())((c, xs) => {
+            val (i, syms) = c match { case (i, set) => (i, set.toList) }
+            xs match {
+              case Nil  => syms map (s => List(Combo(i, s)))
+              case _    => for (s <- syms ; rest <- xs) yield Combo(i, s) :: rest
+            }
+          })
+
+        folded filterNot (combo => rows exists (r => rowCoversCombo(r, combo)))
+      }
+
+      private def mkPad(xs: List[Combo], i: Int): String = xs match {
+        case Nil                    => pad("*")
+        case Combo(j, sym) :: rest  => if (j == i) pad(sym.name.toString) else mkPad(rest, i)
+      }
+      private def mkMissingStr(open: List[Combo]) =
+        "missing combination %s\n" format tvars.indices.map(mkPad(open, _)).mkString
+
+      /** The only public method. */
+      def check = {
+        def errMsg = (inexhaustives map mkMissingStr).mkString
+        if (inexhaustives.nonEmpty)
+          cunit.warning(tvars.head.pos, "match is not exhaustive!\n" + errMsg)
+
+        rep
+      }
+    }
+  }
 }
\ No newline at end of file
diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
index 558d1b0f1f..45a8e5939c 100644
--- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
+++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
@@ -22,7 +22,6 @@ trait ParallelMatching extends ast.TreeDSL
       with Matrix
       with Patterns
       with PatternBindings
-      with PatternOptimizer
 {
   self: ExplicitOuter =>
 
@@ -133,7 +132,7 @@ trait ParallelMatching extends ast.TreeDSL
   def toPats(xs: List[Tree]): List[Pattern] = xs map Pattern.apply
 
   /** The umbrella matrix class. **/
-  class MatchMatrix(val context: MatrixContext, data: MatrixInit) extends MatchMatrixOptimizer {
+  class MatchMatrix(val context: MatrixContext, data: MatrixInit) extends MatchMatrixOptimizer with MatrixExhaustiveness {
     import context._
 
     val MatrixInit(roots, cases, failTree)  = data
@@ -162,7 +161,7 @@ trait ParallelMatching extends ast.TreeDSL
       // shortcut
       if (bx < 0) Apply(ID(shortCuts(-bx-1)), Nil)
       // first time this bx is requested - might be bound elsewhere
-      else if (target.isNotReached) target.createLabelBody("body%"+bx, patternVars, patternValDefs)
+      else if (target.isNotReached) target.createLabelBody(bx, patternVars, patternValDefs)
       // call label "method" if possible
       else target.getLabelBody(idents, patternValDefs)
     }
@@ -748,31 +747,25 @@ trait ParallelMatching extends ast.TreeDSL
 
     /*** States, Rows, Etc. ***/
 
-    case class Row(pat: List[Pattern], subst: Bindings, guard: Guard, bx: Int) {
-      if (pat exists (p => !p.isDefault))
-        traceCategory("Row", "%s", pp(pat))
+    case class Row(pats: List[Pattern], subst: Bindings, guard: Guard, bx: Int) {
+      if (pats exists (p => !p.isDefault))
+        traceCategory("Row", "%s", pp(pats))
 
-      def insert(h: Pattern)              = copy(pat = h :: pat)
-      def insert(hs: List[Pattern])       = copy(pat = hs ::: pat)    // prepends supplied pattern
-      def replace(hs: List[Pattern])      = copy(pat = hs)            // substitutes for patterns
+      def insert(h: Pattern)              = copy(pats = h :: pats)
+      def insert(hs: List[Pattern])       = copy(pats = hs ::: pats)  // prepends supplied pattern
+      def replace(hs: List[Pattern])      = copy(pats = hs)           // substitutes for patterns
       def rebind(b: Bindings)             = copy(subst = b)           // substitutes for bindings
 
       def rebind2(vs: Iterable[Symbol], tvars: Symbol) =
         copy(subst = subst.add(vs, tvars))
 
       def insert2(hs: List[Pattern], vs: Iterable[Symbol], tvars: Symbol) =             // prepends and prepends
-        copy(pat = hs ::: pat, subst = subst.add(vs, tvars))
-
-      /** returns true if the patterns in this rows cover a type symbols "combination" and there is no guard
-       *  @param comb pairs of (column index, type symbol)
-       */
-      def covers(combos: List[Combo]) =
-        guard.isEmpty && (combos forall (c => c isCovered pat(c.index)))
+        copy(pats = hs ::: pats, subst = subst.add(vs, tvars))
 
       // returns this rows with alternatives expanded
       def expandAlternatives(classifyPat: (Pattern, Int) => Pattern): List[Row] = {
         // classify all the top level patterns - alternatives come back unaltered
-        val newPats: List[Pattern] = pat.zipWithIndex map tupled(classifyPat)
+        val newPats: List[Pattern] = pats.zipWithIndex map tupled(classifyPat)
         // expand alternatives if any are present
         (newPats indexWhere (_.isAlternative)) match {
           case -1     => List(replace(newPats))
@@ -782,7 +775,7 @@ trait ParallelMatching extends ast.TreeDSL
             extractBindings(alts.boundTree) map (x => replace(prefix ::: Pattern(x) :: suffix))
         }
       }
-      override def toString() = pp(bx -> (pat, subst))
+      override def toString() = pp(bx -> (pats, subst))
     }
 
     object ExpandedMatrix {
@@ -830,7 +823,8 @@ trait ParallelMatching extends ast.TreeDSL
         abort(msg.format(name, pp(labelParamTypes), pp(idents), pp(vdefs)))
       }
 
-      def createLabelBody(name: String, args: List[Symbol], vdefs: List[Tree]) = {
+      def createLabelBody(index: Int, args: List[Symbol], vdefs: List[Tree]) = {
+        val name = "body%" + index
         require(_labelSym == null)
         referenceCount += 1
 
@@ -866,31 +860,6 @@ trait ParallelMatching extends ast.TreeDSL
 
       override def toString() = pp("Final%d%s".format(bx, pp(freeVars)) -> body)
     }
-
-    case class Combo(index: Int, sym: Symbol) {
-      // is this combination covered by the given pattern?
-      def isCovered(p: Pattern) = {
-        def cmpSymbols(t1: Type, t2: Type)  = t1.typeSymbol eq t2.typeSymbol
-        def coversSym = {
-          val tpe = decodedEqualsType(p.tpe)
-          lazy val lmoc = sym.linkedModuleOfClass
-          val symtpe =
-            if ((sym hasFlag Flags.MODULE) && (lmoc ne NoSymbol))
-              singleType(sym.tpe.prefix, lmoc)   // e.g. None, Nil
-            else sym.tpe
-
-          (tpe.typeSymbol == sym) ||
-          (symtpe <:< tpe) ||
-          (symtpe.parents exists (x => cmpSymbols(x, tpe))) || // e.g. Some[Int] <: Option[&b]
-          ((tpe.prefix memberType sym) <:< tpe)  // outer, see combinator.lexical.Scanner
-        }
-
-        cond(p.tree) {
-          case _: UnApply | _: ArrayValue => true
-          case x                          => p.isDefault || coversSym
-        }
-      }
-    }
     case class Branch[T](action: T, succ: Rep, fail: Option[Rep])
     case class UnapplyCall(ua: Tree, vdefs: List[Tree]) {
       def matchCondition: Tree =
@@ -899,44 +868,32 @@ trait ParallelMatching extends ast.TreeDSL
     }
 
     case class Rep(val tvars: List[Symbol], val rows: List[Row]) {
-      import Flags._
+      lazy val Row(pats, subst, guard, index) = rows.head
+      lazy val guardedRest        = if (guard.isEmpty) NoRep else make(tvars, rows.tail)
+      lazy val (defaults, others) = pats span (_.isDefault)
 
       /** Converts this to a tree - recursively acquires subreps. */
       final def toTree(): Tree = typer typed this.applyRule.tree()
 
-      /** Exhaustiveness checking requires looking for sealed classes
-       *  and if found, making sure all children are covered by a pattern.
-       */
-      private def requiresExhaustive(s: Symbol) =
-         (s hasFlag MUTABLE) &&                 // indicates that have not yet checked exhaustivity
-        !(s hasFlag TRANS_FLAG) &&              // indicates @unchecked
-         (s.tpe.typeSymbol hasFlag SEALED) &&
-         { s resetFlag MUTABLE ; true }         // side effects MUTABLE flag
-
-      private def sealedSymsFor(s: Symbol): Set[Symbol] = {
-        def countSealed(child: Symbol) = {
-          // include base class only if non-abstract
-          def baseSet = if (child hasFlag ABSTRACT) Set() else Set(child)
-          sealedSymsFor(child) ++ baseSet
-        }
-        if (s hasFlag SEALED) s.children flatMap countSealed
-        else Set()
+      /** The VariableRule. */
+      private def variable() = {
+        val binding = (defaults map (_.boundVariables) zip tvars) .
+          foldLeft(subst)((b, pair) => b.add(pair._1, pair._2))
+
+        VariableRule(binding, guard, guardedRest, index)
       }
-      private lazy val inexhaustives: List[List[Combo]] = {
-        val collected =
-          for ((sym, i) <- tvars.zipWithIndex ; if requiresExhaustive(sym)) yield
-            i -> sealedSymsFor(sym.tpe.typeSymbol)
-
-        val folded =
-          collected.foldRight(List[List[Combo]]())((c, xs) => {
-            val (i, syms) = c match { case (i, set) => (i, set.toList) }
-            xs match {
-              case Nil  => syms map (s => List(Combo(i, s)))
-              case _    => for (s <- syms ; rest <- xs) yield Combo(i, s) :: rest
-            }
-          })
 
-        folded filterNot (combo => rows exists (_ covers combo))
+      /** The MixtureRule. */
+      def mixture() = {
+        /** cut out the column containing the non-default pattern. */
+        val newIndex  = defaults.size
+
+        val rpat      = others.head
+        val column    = rpat :: (rows.tail map (_ pats newIndex))
+        val restTemp  = dropIndex(tvars, newIndex)
+        val restRows  = rows map (r => r replace dropIndex(r.pats, newIndex))
+
+        MixtureRule(new Scrutinee(tvars(newIndex)), column, make(restTemp, restRows))
       }
 
       /** Applying the rule will result in one of:
@@ -945,47 +902,15 @@ trait ParallelMatching extends ast.TreeDSL
         *    MixtureRule - if one or more patterns are not default patterns
         *      ErrorRule - if there are no rows remaining
         */
-      final def applyRule(): RuleApplication = {
-        def dropIndex[T](xs: List[T], n: Int) = (xs take n) ::: (xs drop (n + 1))
-
-        lazy val Row(pmatch, subst, guard, index) = rows.head
-        lazy val guardedRest        = if (guard.isEmpty) NoRep else make(tvars, rows.tail)
-        lazy val (defaults, others) = pmatch span (_.isDefault)
-        lazy val ndIndex            = defaults.size   // index of non-default pattern in pmatch
-
+      final def applyRule(): RuleApplication =
         if (rows.isEmpty) ErrorRule()
-        else if (others.isEmpty) {
-          /** top-most rows contains only variables/wildcards */
-          val binding = (defaults map (_.boundVariables) zip tvars) .
-            foldLeft(subst)((b, pair) => b.add(pair._1, pair._2))
-
-          VariableRule(binding, guard, guardedRest, index)
-        }
-        else {
-          /** cut out the column (px) containing the non-default pattern. */
-          val rpat      = others.head
-          val vs        = rpat.boundVariables
-          val column    = rpat :: (rows.tail map (_ pat ndIndex))
-          val restTemp  = dropIndex(tvars, ndIndex)
-          val restRows  = rows map (r => r replace dropIndex(r.pat, ndIndex))
-
-          MixtureRule(new Scrutinee(tvars(ndIndex)), column, make(restTemp, restRows))
-        }
-      }
+        else if (others.isEmpty) variable()
+        else mixture()
 
-      def checkExhaustive: this.type = {
-        if (inexhaustives.nonEmpty) {
-          def mkPad(xs: List[Combo], i: Int): String = xs match {
-            case Nil                    => pad("*")
-            case Combo(j, sym) :: rest  => if (j == i) pad(sym.name.toString) else mkPad(rest, i)
-          }
-          def mkMissingStr(open: List[Combo]) =
-            "missing combination %s\n" format tvars.indices.map(mkPad(open, _)).mkString
+      def checkExhaustive = new ExhaustivenessChecker(this).check
 
-          cunit.warning(tvars.head.pos, "match is not exhaustive!\n" + (inexhaustives map mkMissingStr).mkString)
-        }
-        this
-      }
+      private def dropIndex[T](xs: List[T], n: Int) =
+        (xs take n) ::: (xs drop (n + 1))
 
       override def toString() =
         if (tvars.size == 0) "Rep(%d) = %s".format(rows.size, pp(rows))
diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
index c6a61984bf..6a31a68989 100644
--- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
+++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
@@ -19,7 +19,7 @@ import scala.util.NameTransformer.decode
  *  @author Burak Emir
  */
 trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
-  self: ExplicitOuter with ParallelMatching with PatternOptimizer =>
+  self: ExplicitOuter with ParallelMatching  =>
 
   import global.{ typer => _, _ }
   import analyzer.Typer