The sort of pattern matcher commit which makes ...

The sort of pattern matcher commit which makes water taste better and
birds sing more sweetly. Hard to be more specific than that, but let's
just say that the number of IQ points one has to have on hand to grok
the pattern matcher is down at least 25 from this time last year.

2 files changed, 73 insertions, 98 deletions

diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
index 83b893a252..0f72778bc3 100644
--- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
+++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
@@ -152,16 +152,12 @@ trait ParallelMatching extends ast.TreeDSL {
   import collection.mutable.{ HashMap, ListBuffer }
   class MatchMatrix(context: MatchMatrixContext, data: MatchMatrixInit) {
     import context._
-    val MatchMatrixInit(roots, cases, failTree) = data
 
-    val labels    = new HashMap[Int, Symbol]()
-    val shortCuts = new ListBuffer[Symbol]()
-    lazy val reached   = new BitSet(targets.size)
+    val MatchMatrixInit(roots, cases, failTree) = data
+    val ExpandedMatrix(rows, targets)           = expand(roots, cases)
+    val expansion: Rep                          = make(roots, rows)
 
-    private lazy val expandResult       = expand(roots, cases)
-    lazy val targets: List[FinalState]  = expandResult._2
-    lazy val vss: List[List[Symbol]]    = expandResult._3
-    lazy val expansion: Rep             = make(roots, expandResult._1)
+    val shortCuts   = new ListBuffer[Symbol]()
 
     final def shortCut(theLabel: Symbol): Int = {
       shortCuts += theLabel
@@ -187,8 +183,9 @@ trait ParallelMatching extends ast.TreeDSL {
       object lxtt extends Transformer {
         override def transform(tree: Tree): Tree = tree match {
           case blck @ Block(vdefs, ld @ LabelDef(name, params, body)) =>
-            val bx = labelIndex(ld.symbol)
-            if (bx >= 0 && !isReachedTwice(bx)) squeezedBlock(vdefs, body)
+            def shouldInline(t: FinalState) = t.isReachedOnce && (t.label eq ld.symbol)
+
+            if (targets exists shouldInline) squeezedBlock(vdefs, body)
             else blck
 
           case t =>
@@ -218,78 +215,50 @@ trait ParallelMatching extends ast.TreeDSL {
       returning[Tree](resetTraverser traverse _)(lxtt transform tree)
     }
 
-    final def isReached(bx: Int)        = labels contains bx
-    final def markReachedTwice(bx: Int) { reached += bx }
-
-    /** @pre bx < 0 || labelIndex(bx) != -1 */
-    final def isReachedTwice(bx: Int) = (bx < 0) || reached(bx)
-
-    /* @returns bx such that labels(bx) eq label, -1 if no such bx exists */
-    final def labelIndex(label: Symbol) = labels find (_._2 eq label) map (_._1) getOrElse (-1)
-
     /** first time bx is requested, a LabelDef is returned. next time, a jump.
      *  the function takes care of binding
      */
     final def requestBody(bx: Int, subst: Bindings): Tree = {
-      if (bx < 0) { // is shortcut
-        val jlabel = shortCuts(-bx-1)
-        return Apply(ID(jlabel), Nil)
-      }
-      if (!isReached(bx)) { // first time this bx is requested
+      val target = targets(bx)
+      lazy val FinalState(bindings, body, freeVars) = target
+
+      // shortcut
+      def labelJump: Tree = Apply(ID(shortCuts(-bx-1)), Nil)
+
+      // first time this bx is requested
+      def firstTime: Tree = {
         // might be bound elsewhere
         val (vsyms, vdefs) : (List[Symbol], List[Tree]) = List.unzip(
-          for (v <- vss(bx) ; substv <- subst(v)) yield
+          for (v <- freeVars ; substv <- subst(v)) yield
             (v, typedValDef(v, substv))
         )
 
-        val body    = targets(bx).body
         // @bug: typer is not able to digest a body of type Nothing being assigned result type Unit
-        val tpe     = if (body.tpe.isNothing) body.tpe else resultType
-        val newType = MethodType(vsyms, tpe)
-        val label   = owner.newLabel(body.pos, "body%"+bx) setInfo newType
-        labels(bx)  = label
+        val tpe       = if (body.tpe.isNothing) body.tpe else resultType
+        target.setLabel(owner.newLabel(body.pos, "body%"+bx) setInfo MethodType(vsyms, tpe))
 
-        return logAndReturn("requestBody(%d) first time: ".format(bx), squeezedBlock(vdefs, (
-          if (isLabellable(body)) LabelDef(label, vsyms, body setType tpe)
+        squeezedBlock(vdefs, (
+          if (isLabellable(body)) LabelDef(target.label, vsyms, body setType tpe)
           else body.duplicate setType tpe
-        )))
+        ))
       }
 
-      // if some bx is not reached twice, its LabelDef is replaced with body itself
-      markReachedTwice(bx)
-
-      val args  = vss(bx) map subst flatten
-      val label = labels(bx)
-      val body  = targets(bx).body
-      val fmls  = label.tpe.paramTypes
+      def successiveTimes: Tree = {
+        val args  = freeVars map subst flatten
+        val fmls  = target.label.tpe.paramTypes
+        def vds   = for (v <- freeVars ; substv <- subst(v)) yield typedValDef(v, substv)
 
-      def debugConsistencyFailure(): String = {
-        val xs =
-          ( for ((vs, i) <- vss.zipWithIndex) yield "vss(%d) = %s\nargs = %s".format(i, vs mkString ", ", args) ) ++
-          ( for ((t, i) <- targets.zipWithIndex) yield "targets(%d) = %s".format(i, t) ) ++
-          ( for ((i, l) <- labels) yield "labels(%d) = %s".format(i, l) ) ++
-          ( for ((s, v) <- List("bx" -> bx, "label.tpe" -> label.tpe)) yield "%s = %s".format(s, v) )
-
-        xs mkString "\n"
-      }
-      // sanity checks: same length lists and args are conformant with formals
-      def isConsistent() = (fmls.length == args.length) && List.forall2(args, fmls)(_.tpe <:< _)
-
-      if (!isConsistent()) {
-        val msg = (
-          """Consistency problem compiling %s!
-            |Trying to call %s(%s) with arguments (%s)""" .
-            stripMargin.format(cunit.source, label, fmls, args)
-        )
-        println(debugConsistencyFailure())
-        // TRACE(debugConsistencyFailure())
-        cunit.error(body.pos, msg)
+        if (isLabellable(body)) ID(target.label) APPLY (args)
+        else                    squeezedBlock(vds, body.duplicate setType resultType)
       }
 
-      def vds = for (v <- vss(bx) ; substv <- subst(v)) yield typedValDef(v, substv)
+      if (bx < 0) labelJump
+      else {
+        target.incrementReached
 
-      if (isLabellable(body)) ID(label) APPLY (args)
-      else                    squeezedBlock(vds, body.duplicate setType resultType)
+        if (target.isReachedOnce) firstTime
+        else successiveTimes
+      }
     }
 
     /** the injection here handles alternatives and unapply type tests */
@@ -367,21 +336,10 @@ trait ParallelMatching extends ast.TreeDSL {
       else Rep(tvars, rows).checkExhaustive
     }
 
-    override def toString() = {
-      val toPrint: List[(Any, Traversable[Any])] = (
-        (vss.zipWithIndex map (_.swap)) :::
-        List[(Any, Traversable[Any])](
-          "labels" -> labels,
-          "targets" -> targets,
-          "reached" -> reached,
-          "shortCuts" -> shortCuts.toList
-        ) filterNot (_._2.isEmpty)
-      )
+    override def toString() = "MatchMatrix(%s)".format(targets)
 
-      val strs = toPrint map { case (k, v) => "    %s = %s\n".format(k, v) }
-      if (toPrint.isEmpty) "MatchMatrix()"
-      else "MatchMatrix(\n%s)".format(strs mkString)
-    }
+    /** Intended to be the DFA created from the match matrix. */
+    class MatchAutomaton(matrix: MatchMatrix) { }
 
     /**
      * Encapsulates a symbol being matched on.
@@ -1099,7 +1057,32 @@ trait ParallelMatching extends ast.TreeDSL {
       }
     }
 
-    case class FinalState(subst: Bindings, body: Tree)
+    object ExpandedMatrix {
+      def unapply(x: ExpandedMatrix) = Some(x.rows, x.targets)
+      def apply(rows: List[Row], targets: List[FinalState]) = new ExpandedMatrix(rows, targets)
+    }
+    class ExpandedMatrix(val rows: List[Row], val targets: List[FinalState])
+
+    abstract class State {
+      def bindings: Bindings
+      def body: Tree
+      def freeVars: List[Symbol]
+      def isFinal: Boolean
+    }
+
+    case class FinalState(bindings: Bindings, body: Tree, freeVars: List[Symbol]) extends State {
+      private var referenceCount = 0
+      private var _label: Symbol = null
+      def incrementReached: Unit =    { referenceCount += 1 }
+      def setLabel(s: Symbol): Unit = { _label = s }
+      def label = _label
+
+      def isFinal = true
+      def isNotReached = referenceCount == 0
+      def isReachedOnce = referenceCount == 1
+      def isReachedTwice = referenceCount > 1
+    }
+
 
     case class Combo(index: Int, sym: Symbol) {
       // is this combination covered by the given pattern?
@@ -1143,10 +1126,12 @@ trait ParallelMatching extends ast.TreeDSL {
         case (i, syms) :: cs  => for (s <- syms.toList; rest <- combine(cs)) yield Combo(i, s) :: rest
       }
 
-      /*   internal representation is (tvars:List[Symbol], rows:List[Row])
-       *
-       *         tmp1       tmp_m
-       */
+      /** Applying the rule will result in one of:
+        *
+        *   VariableRule - if all patterns are default patterns
+        *    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))
 
@@ -1236,10 +1221,9 @@ trait ParallelMatching extends ast.TreeDSL {
     }
 
     val NoRep = Rep(Nil, Nil)
-
     /** Expands the patterns recursively. */
-    final def expand(roots: List[Symbol], cases: List[Tree]): (List[Row], List[FinalState], List[List[Symbol]]) = {
-      val res = unzip3(
+    final def expand(roots: List[Symbol], cases: List[Tree]): ExpandedMatrix = {
+      val (rows, finals) = List.unzip(
         for ((CaseDef(pat, guard, body), index) <- cases.zipWithIndex) yield {
           def mkRow(ps: List[Tree]) = Row(toPats(ps), NoBinding, Guard(guard), index)
 
@@ -1248,11 +1232,11 @@ trait ParallelMatching extends ast.TreeDSL {
             case Apply(fn, args)        => mkRow(args)
             case WILD()                 => mkRow(getDummies(roots.length))
           }
-          (rowForPat, FinalState(NoBinding, body), definedVars(pat))
+          (rowForPat, FinalState(NoBinding, body, definedVars(pat)))
         }
       )
 
-      res match { case (rows, finals, vars) => (rows flatMap (x => x), finals, vars) }
+      new ExpandedMatrix(rows flatMap (x => x), finals)
     }
 
     /** returns the condition in "if (cond) k1 else k2"
diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
index 0618608e5a..78896846a4 100644
--- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
+++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
@@ -203,16 +203,7 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
     val dfatree = typer typed Block(vars, mch)        // packages into a code block
 
     // redundancy check
-    for ((cs, bx) <- cases.zipWithIndex) {
-      // if (!matrix.isReached(bx)) {
-      //   println("cases = %s".format(cases))
-      //   println("matrix = %s, rep = %s".format(matrix, rep))
-      //   println("dfatree = " + toCompactString(dfatree))
-      // }
-      if (!matrix.isReached(bx))
-        cunit.error(cs.body.pos, "unreachable code")
-    }
-
+    matrix.targets filter (_.isNotReached) foreach (cs => cunit.error(cs.body.pos, "unreachable code"))
     // cleanup performs squeezing and resets any remaining TRANS_FLAGs
     matrix cleanup dfatree
   }