Mostly, a pile of pattern matcher tracing code.

4 files changed, 165 insertions, 123 deletions

diff --git a/src/compiler/scala/tools/nsc/matching/Matrix.scala b/src/compiler/scala/tools/nsc/matching/Matrix.scala
index 527c01b1a8..77ad04b877 100644
--- a/src/compiler/scala/tools/nsc/matching/Matrix.scala
+++ b/src/compiler/scala/tools/nsc/matching/Matrix.scala
@@ -15,6 +15,7 @@ trait Matrix extends PatternOptimizer {
   import global.{ typer => _, _ }
   import analyzer.Typer
   import CODE._
+  import Debug._
 
   /** Translation of match expressions.
    *
@@ -95,19 +96,13 @@ trait Matrix extends PatternOptimizer {
     {
       val n: Name = if (name == null) newName(pos, "temp") else name
       // careful: pos has special meaning
-      traceAndReturn("[newVar] ", owner.newVariable(pos, n) setInfo tpe setFlag (0L /: flags)(_|_))
-    }
+      val res = owner.newVariable(pos, n) setInfo tpe setFlag (0L /: flags)(_|_)
 
-    def typedValDef(x: Symbol, rhs: Tree) = {
-      val finalRhs = x.tpe match {
-        case WildcardType   =>
-          rhs setType null
-          x setInfo (typer typed rhs).tpe
-          rhs
-        case _              =>
-          typer.typed(rhs, x.tpe)
-      }
-      traceAndReturn("[typedValDef] ", typer typed (VAL(x) === finalRhs))
+      traceCategory("newVar", "%s: %s", res, tpe)
+      res
     }
+
+    def typedValDef(x: Symbol, rhs: Tree) =
+      tracing("typedVal", typer typedValDef (VAL(x) === rhs))
   }
 }
\ 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 12a3ac99c2..d06ef94432 100644
--- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
+++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
@@ -31,6 +31,9 @@ trait ParallelMatching extends ast.TreeDSL
   import treeInfo.{ isStar }
   import CODE._
 
+  /** Debugging support: enable with -Ypmat-debug **/
+  private final def trace = settings.Ypmatdebug.value
+
   object Types {
     import definitions._
     implicit def enrichType(x: Type): RichType = new RichType(x)
@@ -52,25 +55,76 @@ trait ParallelMatching extends ast.TreeDSL
   }
   import Types._
 
-  /** Debugging support: enable with -Ypmat-debug **/
-  private final def trace = settings.Ypmatdebug.value
+  object Debug {
+    def typeToString(t: Type): String = t match {
+      case NoType => "x"
+      case x      => x.toString
+    }
+    def symbolToString(s: Symbol): String = s match {
+      case x  => x.toString
+    }
+    def treeToString(t: Tree): String = unbind(t) match {
+      case EmptyTree            => "?"
+      case WILD()               => "_"
+      case Literal(Constant(x)) => "LIT(%s)".format(x)
+      case Apply(fn, args)      => "%s(%s)".format(treeToString(fn), args map treeToString mkString ",")
+      case x: TypeTree          => "TT(%s)".format(symbolToString(x.symbol))
+      case Typed(expr, tpt)     => "%s: %s".format(treeToString(expr), treeToString(tpt))
+      case x                    =>  x.toString + " (" + x.getClass + ")"
+    }
+
+    // pretty print for debugging
+    def pp(x: Any): String = pp(x, false)
+    def pp(x: Any, newlines: Boolean): String = {
+      def clean(s: String): String = s.replaceAll("""java\.lang\.""", "")
 
-  def ifDebug(body: => Unit): Unit          = { if (settings.debug.value) body }
-  def DBG(msg: => String): Unit             = { ifDebug(println(msg)) }
+      val elems: List[Any] = x match {
+        case x: String      => return clean(x)
+        case xs: List[_]    => xs
+        case x: Tuple2[_,_] => return pp(x._1) + " -> " + pp(x._2)
+        case x              => return pp(x.toString)
+      }
+      def pplist(xs: List[Any]): String = {
+        val xs2 = xs map pp
+
+        if (newlines) (xs2 map ("    " + _ + "\n")).mkString("\n", "", "")
+        else xs2.mkString("(", ", ", ")")
+      }
+
+      pplist(elems)
+    }
 
-  // @elidable(elidable.FINE)
-  def TRACE(f: String, xs: Any*): Unit      = { if (trace) println(if (xs.isEmpty) f else f.format(xs : _*)) }
-  def traceAndReturn[T](s: String, x: T): T = { TRACE(s + x.toString) ; x }
+    def ifDebug(body: => Unit): Unit          = { if (settings.debug.value) body }
+    def DBG(msg: => String): Unit             = { ifDebug(println(msg)) }
 
-  def indent(s: Any) = s.toString() split "\n" map ("  " + _) mkString "\n"
-  def indentAll(s: Seq[Any]) = s map ("  " + _.toString() + "\n") mkString
+    // @elidable(elidable.FINE)
+    def TRACE(f: String, xs: Any*): Unit      = { if (trace) println(pp(if (xs.isEmpty) f else f.format(xs : _*))) }
+
+    def tracing2[T](x: T)(category: String, xs: String*) = {
+      val preamble = "[" + """%10s""".format(category) + "]  "
+      if (xs.isEmpty) TRACE(preamble, x)
+      else TRACE(preamble + xs.head, xs.tail: _*)
+
+      x
+    }
+
+    def tracing[T](s: String, x: T): T = {
+      TRACE("[" + """%10s""".format(s) + "]  " + x.toString)
+      x
+    }
+    def traceCategory(cat: String, f: String, xs: Any*) =
+      TRACE("[" + """%10s""".format(cat) + "]  " + f, xs: _*)
+
+    def indent(s: Any) = s.toString() split "\n" map ("  " + _) mkString "\n"
+    def indentAll(s: Seq[Any]) = s map ("  " + _.toString() + "\n") mkString
+  }
+  import Debug._
 
   /** Transition **/
   def isRightIgnoring(t: Tree) = cond(unbind(t)) { case ArrayValue(_, xs) if !xs.isEmpty => isStar(xs.last) }
   def toPats(xs: List[Tree]): List[Pattern] = xs map Pattern.apply
 
-  /** Back to the regular schedule. **/
-
+  /** The umbrella matrix class. **/
   class MatchMatrix(val context: MatrixContext, data: MatrixInit) extends MatchMatrixOptimizer {
     import context._
 
@@ -90,10 +144,13 @@ trait ParallelMatching extends ast.TreeDSL
      */
     final def requestBody(bx: Int, subst: Bindings): Tree = {
       implicit val ctx = context
-      lazy val target @ FinalState(bindings, body, freeVars) = targets(bx)
+      lazy val target @ FinalState(tbx, body, freeVars) = targets(bx)
       lazy val substInfo = subst infoFor freeVars
       import substInfo._
 
+      // XXX when is this not true?
+      // assert(tbx == bx)
+
       // shortcut
       if (bx < 0) Apply(ID(shortCuts(-bx-1)), Nil)
       // first time this bx is requested - might be bound elsewhere
@@ -141,7 +198,7 @@ trait ParallelMatching extends ast.TreeDSL
 
       // sequences
       def seqType   = tpe.widen baseType SeqClass
-      def elemType  = tpe typeArgs 0  // can this happen? if (seqType == NoType) error("...")
+      def elemType  = tpe typeArgs 0
 
       def newVarOfTpe(tpe: Type) = newVar(pos, tpe, flags)
       def newVarOfSeqType = newVar(pos, seqType)
@@ -207,7 +264,7 @@ trait ParallelMatching extends ast.TreeDSL
       }
 
       def mkRule(rest: Rep): RuleApplication = {
-        traceAndReturn("[mkRule] ", head.tree match {
+        tracing("Rule", head.tree match {
             case x if isEquals(x.tpe)                 => new MixEquals(this, rest)
             case x: ArrayValue                        => new MixSequence(this, rest)
             case AnyUnapply(false)                    => new MixUnapply(this, rest, false)
@@ -260,13 +317,8 @@ trait ParallelMatching extends ast.TreeDSL
       /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */
       def tree(): Tree
 
-      override def toString = {
-        "Rule/%s (%s =^= %s) {\n%s}".format(
-          getClass.getSimpleName,
-          scrut, head,
-          indentAll(patterns)
-        )
-      }
+      override def toString =
+        "Rule/%s (%s =^= %s)".format(getClass.getSimpleName, scrut, head)
     }
 
     case class ErrorRule() extends RuleApplication {
@@ -652,8 +704,13 @@ trait ParallelMatching extends ast.TreeDSL
       ) match { case (x,y,z) => (join(x), join(y), join(z)) }
 
       override def toString = {
-        super.toString() +
-        indentAll(List("moreSpecific: " + moreSpecific, "subsumed: " + subsumed, "remaining: " + remaining))
+        val msgs = List(
+          "moreSpecific: " + pp(moreSpecific),
+          "    subsumed: " + pp(subsumed),
+          "   remaining: " + pp(remaining)
+        )
+
+        super.toString() + "\n" + indentAll(msgs)
       }
 
       /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */
@@ -716,6 +773,9 @@ 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))
+
       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
@@ -746,64 +806,89 @@ trait ParallelMatching extends ast.TreeDSL
             extractBindings(alts.boundTree) map (x => replace(prefix ::: Pattern(x) :: suffix))
         }
       }
-      override def toString() = {
-        val str = indent(
-          "%s\n%s\n%s\n".format(
-            subst, pat.mkString("\n"), guard
-          )
-        )
-        "Row(%d) {\n%s}".format(bx, str)
-      }
+      override def toString() = pp(bx -> (pat, subst))
     }
 
     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])
+    class ExpandedMatrix(val rows: List[Row], val targets: List[FinalState]) {
+      require(rows.size == targets.size)
+
+      override def toString() =
+        "ExpandedMatrix(%d)".format(rows.size) + pp(rows zip targets, true)
+    }
 
     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 {
+    case class FinalState(bx: Int, body: Tree, freeVars: List[Symbol]) extends State {
       private var referenceCount = 0
-      private var _label: Symbol = null
-      def setLabel(s: Symbol): Unit = { _label = s }
+      private var _label: LabelDef = null
+      private var _labelSym: Symbol = null
+
+      def labelSym = _labelSym
       def label = _label
 
+      // @bug: typer is not able to digest a body of type Nothing being assigned result type Unit
+      def bodyTpe = if (body.tpe.isNothing) body.tpe else matchResultType
+      def duplicate = body.duplicate setType bodyTpe
+
+      def isFinal = true
+      def isLabellable = !cond(body)  { case _: Throw | _: Literal => true }
+      def isNotReached = referenceCount == 0
+      def isReachedOnce = referenceCount == 1
+      def isReachedTwice = referenceCount > 1
+
       // arguments to pass to this body%xx
       def labelParamTypes = label.tpe.paramTypes
 
+      private def consistencyFailure(idents: List[Tree], vdefs: List[Tree]) = {
+        val LabelDef(name, params, rhs) = label
+
+        val msg = "Consistency failure in generated block %s(%s):\n  idents = %s\n  vdefs = %s\n"
+        abort(msg.format(name, pp(labelParamTypes), pp(idents), pp(vdefs)))
+      }
+
       def createLabelBody(name: String, args: List[Symbol], vdefs: List[Tree]) = {
-        require(_label == null)
-        _label = owner.newLabel(body.pos, name) setInfo MethodType(args, tpe)
+        require(_labelSym == null)
         referenceCount += 1
 
-        squeezedBlock(vdefs,
-          if (isLabellable) LabelDef(label, args, body setType tpe)
-          else duplicate
-        )
+        if (isLabellable) {
+          // val mtype = MethodType(freeVars, bodyTpe)
+          val mtype = MethodType(args, bodyTpe)
+          _labelSym = owner.newLabel(body.pos, name) setInfo mtype
+
+          TRACE("Creating index %d: mtype = %s".format(bx, mtype))
+          if (freeVars.size != args.size)
+            TRACE("We will be hosed! freeVars = %s, args = %s, vdefs = %s".format(freeVars, args, vdefs))
+
+          // Labelled expression - the symbols in the array (must be Idents!)
+          // are those the label takes as argument
+          _label = typer typedLabelDef LabelDef(_labelSym, args, body setType bodyTpe)
+          TRACE("[New label] def %s%s: %s = %s".format(name, pp(args), bodyTpe, body))
+        }
+
+        ifLabellable(vdefs, squeezedBlock(vdefs, label))
       }
 
       def getLabelBody(idents: List[Tree], vdefs: List[Tree]): Tree = {
         referenceCount += 1
-        if (isLabellable) ID(label) APPLY (idents)
-        else squeezedBlock(vdefs, duplicate)
+        // if (idents.size != labelParamTypes.size)
+        //   consistencyFailure(idents, vdefs)
+
+        ifLabellable(vdefs, ID(labelSym) APPLY (idents))
       }
 
-      // @bug: typer is not able to digest a body of type Nothing being assigned result type Unit
-      def tpe = if (body.tpe.isNothing) body.tpe else matchResultType
-      def duplicate = body.duplicate setType tpe
+      private def ifLabellable(vdefs: List[Tree], t: => Tree) =
+        if (isLabellable) t
+        else squeezedBlock(vdefs, duplicate)
 
-      def isFinal = true
-      def isLabellable = !cond(body)  { case _: Throw | _: Literal => true }
-      def isNotReached = referenceCount == 0
-      def isReachedOnce = referenceCount == 1
-      def isReachedTwice = referenceCount > 1
+      override def toString() = pp("Final%d%s".format(bx, pp(freeVars)) -> body)
     }
 
     case class Combo(index: Int, sym: Symbol) {
@@ -830,7 +915,6 @@ trait ParallelMatching extends ast.TreeDSL
         }
       }
     }
-    case class SetCombo(index: Int, syms: Set[Symbol]) {}
     case class Branch[T](action: T, succ: Rep, fail: Option[Rep])
     case class UnapplyCall(ua: Tree, args: List[Tree])
 
@@ -917,46 +1001,17 @@ trait ParallelMatching extends ast.TreeDSL
         this
       }
 
-      // a fancy toString method for debugging
       override def toString() = {
-        val tempStr = (tvars map (t => pad(t.name))).mkString
-        val underlines = tempStr.replaceAll("""\S""", "-")
-        val rowStr = (
-          for (Row(pat, subst, guard, bx) <- rows) yield {
-            val extraStr: String = guard.toString + subst
-            "%s %s\n".format(pat map pad mkString, extraStr)
-          }
-        ) mkString
-
-        if (tvars.size == 0) "Rep(%dx%d)".format(tvars.size, rows.size)
-        else "Rep(%dx%d)\n%s\n%s\n%s".format(tvars.size, rows.size, tempStr, underlines, rowStr)
-      }
-
-      private val NPAD = 15
-
-      private def typeToString(t: Type): String = t match {
-        case NoType => "x"
-        case x      => x.toString
-      }
-      private def symbolToString(s: Symbol): String = s match {
-        case x  => x.toString
-      }
-      private def treeToString(t: Tree): String = unbind(t) match {
-        case EmptyTree            => "?"
-        case WILD()               => "_"
-        case Literal(Constant(x)) => "LIT(%s)".format(x)
-        case Apply(fn, args)      => "%s(%s)".format(treeToString(fn), args map treeToString mkString ",")
-        case x: TypeTree          => "TT(%s)".format(symbolToString(x.symbol))
-        case Typed(expr, tpt)     => "%s: %s".format(treeToString(expr), treeToString(tpt))
-        case x                    =>  x.toString + " (" + x.getClass + ")"
+        if (tvars.size == 0) "Rep(%d) = %s".format(rows.size, pp(rows))
+        else "Rep(%dx%d)\n  %s\n  %s".format(tvars.size, rows.size, pp(tvars), pp(rows))
       }
 
       private def pad(s: Any): String = pad(s match {
         case x: Tree    => treeToString(x)
-        // case x: AnyRef  => x.toString + " (" + x.getClass + ")"
-        case x                  => x.toString
+        case x          => x.toString
       })
-      private def pad(s: String): String = "%%%ds" format (NPAD - 1) format s
+      private val NPAD = 15
+      private def pad(s: String): String = "%%%ds" format (NPAD-1) format s
     }
 
     val NoRep = Rep(Nil, Nil)
@@ -973,11 +1028,11 @@ trait ParallelMatching extends ast.TreeDSL
             case WILD()                 => emptyTrees(roots.length)
           })
 
-          (row, FinalState(NoBinding, body, pattern.definedVars))
+          (row, FinalState(index, body, pattern.definedVars))
         }
       )
 
-      new ExpandedMatrix(rows, finals)
+      tracing("Expanded", new ExpandedMatrix(rows, finals))
     }
 
     /** returns the condition in "if (cond) k1 else k2"
diff --git a/src/compiler/scala/tools/nsc/matching/PatternBindings.scala b/src/compiler/scala/tools/nsc/matching/PatternBindings.scala
index 6450962391..92174b0018 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternBindings.scala
+++ b/src/compiler/scala/tools/nsc/matching/PatternBindings.scala
@@ -16,6 +16,7 @@ trait PatternBindings extends ast.TreeDSL
   import global.{ typer => _, _ }
   import definitions.{ EqualsPatternClass }
   import CODE._
+  import Debug._
 
   /** EqualsPattern **/
   def isEquals(tpe: Type)           = cond(tpe) { case TypeRef(_, EqualsPatternClass, _) => true }
@@ -116,6 +117,8 @@ trait PatternBindings extends ast.TreeDSL
     def castIfNeeded  =
       if (tvar.tpe <:< pvar.tpe) ID(tvar)
       else ID(tvar) AS_ANY pvar.tpe
+
+    override def toString() = pp(pvar -> tvar)
   }
 
   case class BindingsInfo(xs: List[Binding]) {
@@ -129,6 +132,7 @@ trait PatternBindings extends ast.TreeDSL
   }
 
   class Bindings(private val vlist: List[Binding]) extends Function1[Symbol, Option[Ident]] {
+    traceCategory("Bindings", this.toString)
     def vmap(v: Symbol): Option[Binding] = vlist find (_.pvar eq v)
 
     // filters the given list down to those defined in these bindings
@@ -141,7 +145,7 @@ trait PatternBindings extends ast.TreeDSL
     }
     def apply(v: Symbol): Option[Ident] = vmap(v) map (_.toIdent)
 
-    override def toString() = " Bound(%s)".format(vlist)
+    override def toString() = pp(vlist)
   }
 
   val NoBinding: Bindings = new Bindings(Nil)
diff --git a/src/compiler/scala/tools/nsc/matching/Patterns.scala b/src/compiler/scala/tools/nsc/matching/Patterns.scala
index 35406d097f..b346aec329 100644
--- a/src/compiler/scala/tools/nsc/matching/Patterns.scala
+++ b/src/compiler/scala/tools/nsc/matching/Patterns.scala
@@ -9,24 +9,9 @@ package matching
 import symtab.Flags
 import util.NoPosition
 
-/**
- * Simple pattern types:
+/** Patterns are wrappers for Trees with enhanced semantics.
  *
- * 1 Variable               x
- * 3 Literal                56
- *
- * Types which must be decomposed into conditionals and simple types:
- *
- * 2 Typed                  x: Int
- * 4 Stable Identifier      Bob or `x`
- * 5 Constructor            Symbol("abc")
- * 6 Tuple                  (5, 5)
- * 7 Extractor              List(1, 2)
- * 8 Sequence               List(1, 2, _*)
- * 9 Infix                  5 :: xs
- * 10 Alternative           "foo" | "bar"
- * 11 XML                   --
- * 12 Regular Expression    --
+ *  @author Paul Phillips
  */
 
 trait Patterns extends ast.TreeDSL {
@@ -35,6 +20,7 @@ trait Patterns extends ast.TreeDSL {
   import global.{ typer => _, _ }
   import definitions._
   import CODE._
+  import Debug._
   import treeInfo.{ unbind, isVarPattern }
 
   // Fresh patterns
@@ -74,7 +60,7 @@ trait Patterns extends ast.TreeDSL {
       case ExtractorPattern(ua) if testVar.tpe <:< tpt.tpe  => this rebindTo expr
       case _                                                => this
     }
-    override def toString() = "%s: %s".format(expr, tpt)
+    override def toString() = "%s: %s".format(Pattern(expr), tpt)
   }
 
   // 8.1.3
@@ -271,6 +257,8 @@ trait Patterns extends ast.TreeDSL {
   // XMLPattern ... for now, subsumed by SequencePattern, but if we want
   //   to make it work right, it probably needs special handling.
 
+  private def abortUnknownTree(tree: Tree) =
+    abort("Unknown Tree reached pattern matcher: %s/%s".format(tree, tree.getClass))
 
   object Pattern {
     // a small tree -> pattern cache
@@ -294,7 +282,7 @@ trait Patterns extends ast.TreeDSL {
         case x: ArrayValue        => SequencePattern(x)
         case x: Select            => StableIdPattern(x)
         case x: Star              => StarPattern(x)
-        case _                    => abort("Unknown Tree reached pattern matcher: %s/%s".format(tree, tree.getClass))
+        case _                    => abortUnknownTree(tree)
       }
       cache(tree) = p
 
@@ -302,7 +290,7 @@ trait Patterns extends ast.TreeDSL {
       p match {
         case WildcardPattern()  => p
         case _: LiteralPattern  => p
-        case _                  => traceAndReturn("[New Pattern] ", p)
+        case _                  => tracing("Pattern", p)
       }
     }
     def unapply(other: Any): Option[(Tree, List[Symbol])] = other match {
@@ -363,7 +351,7 @@ trait Patterns extends ast.TreeDSL {
           case _: Select  => ApplySelectPattern(x)
         }
       }
-      else abort("Strange apply: %s/%s".format(x))
+      else abortUnknownTree(x)
     }
   }