Removed a pile of gratuitous implicit parameter...

Removed a pile of gratuitous implicit parameters from the pattern
matcher. Moved many things to more believable locations. Transitioned
everything in CodeFactory and deleted it.

6 files changed, 936 insertions, 897 deletions

diff --git a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala
index 229a650477..d25861ee39 100644
--- a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala
+++ b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala
@@ -19,10 +19,20 @@ trait TreeDSL {
   import gen.{ scalaDot }
 
   object CODE {
+    // clarity aliases
+    type TreeFunction1 = Tree => Tree
+    type TreeFunction2 = (Tree, Tree) => Tree
+
     // Create a conditional based on a partial function - for values not defined
     // on the partial, it is false.
     def cond[T](x: T)(f: PartialFunction[T, Boolean]) = (f isDefinedAt x) && f(x)
 
+    // strip bindings to find what lies beneath
+    final def unbind(x: Tree): Tree = x match {
+      case Bind(_, y) => unbind(y)
+      case y          => y
+    }
+
     object LIT extends (Any => Literal) {
       def apply(x: Any)   = Literal(Constant(x))
       def unapply(x: Any) = x match {
diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala
deleted file mode 100644
index 2b25b2c49c..0000000000
--- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala
+++ /dev/null
@@ -1,99 +0,0 @@
-/* NSC -- new Scala compiler
- * Copyright 2005-2009 LAMP/EPFL
- * @author Burak Emir
- */
-// $Id$
-
-package scala.tools.nsc.matching
-
-import scala.tools.nsc.util.Position
-
-/** Helper methods that build trees for pattern matching.
- *
- *  @author Burak Emir
- */
-trait CodeFactory extends ast.TreeDSL
-{
-  self: transform.ExplicitOuter with PatternNodes =>
-
-  import global.{ typer => _, _ }
-  import analyzer.Typer
-  import definitions._
-  import CODE._
-
-  // strip bindings to find what tree lies underneath
-  def unbind(x: Tree): Tree = x match {
-    case Bind(_, y) => unbind(y)
-    case y          => y
-  }
-
-  final def typedValDef(x: Symbol, rhs: Tree)(implicit typer: Typer) = {
-    val finalRhs = x.tpe match {
-      case WildcardType   =>
-        rhs setType null
-        x setInfo (typer typed rhs).tpe
-        rhs
-      case _              =>
-        typer.typed(rhs, x.tpe)
-    }
-    typer typed (VAL(x) === finalRhs)
-  }
-
-  final def squeezedBlock(vds: List[Tree], exp: Tree)(implicit theOwner: Symbol): Tree =
-    if (settings_squeeze) Block(Nil, squeezedBlock1(vds, exp))
-    else                  Block(vds, exp)
-
-  final def squeezedBlock1(vds: List[Tree], exp: Tree)(implicit theOwner: Symbol): Tree = {
-    class RefTraverser(sym: Symbol) extends Traverser {
-      var nref, nsafeRef = 0
-      override def traverse(tree: Tree) = tree match {
-        case t: Ident if t.symbol eq sym =>
-          nref += 1
-          if (sym.owner == currentOwner) // oldOwner should match currentOwner
-            nsafeRef += 1
-
-        case LabelDef(_, args, rhs) =>
-          (args dropWhile(_.symbol ne sym)) match {
-            case Nil  =>
-            case _    => nref += 2  // cannot substitute this one
-          }
-          traverse(rhs)
-        case t if nref > 1 =>       // abort, no story to tell
-        case t =>
-          super.traverse(t)
-      }
-    }
-
-    class Subst(sym: Symbol, rhs: Tree) extends Transformer {
-      var stop = false
-      override def transform(tree: Tree) = tree match {
-        case t: Ident if t.symbol == sym =>
-          stop = true
-          rhs
-        case _ => if (stop) tree else super.transform(tree)
-      }
-    }
-
-    lazy val squeezedTail = squeezedBlock(vds.tail, exp)
-    def default = squeezedTail match {
-      case Block(vds2, exp2) => Block(vds.head :: vds2, exp2)
-      case exp2              => Block(vds.head :: Nil,  exp2)
-    }
-
-    if (vds.isEmpty) exp
-    else vds.head match {
-      case vd: ValDef =>
-        val sym = vd.symbol
-        val rt = new RefTraverser(sym)
-        rt.atOwner (theOwner) (rt traverse squeezedTail)
-
-        rt.nref match {
-          case 0                      => squeezedTail
-          case 1 if rt.nsafeRef == 1  => new Subst(sym, vd.rhs) transform squeezedTail
-          case _                      => default
-        }
-      case _          =>
-        default
-    }
-  }
-}
diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
index 7ce01f9c48..d6b0592989 100644
--- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
+++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala
@@ -26,10 +26,16 @@ import MatchUtil._
  *
  *    Row( p_m1  ...  p_mn   g_m  b_m ) + subst
  *
+ * Implementation based on the algorithm described in
+ *
+ *   "A Term Pattern-Match Compiler Inspired by Finite Automata Theory"
+ *   Mikael Pettersson
+ *   ftp://ftp.ida.liu.se/pub/labs/pelab/papers/cc92pmc.ps.gz
+ *
  *  @author Burak Emir
  */
 trait ParallelMatching extends ast.TreeDSL {
-  self: transform.ExplicitOuter with PatternNodes with CodeFactory =>
+  self: transform.ExplicitOuter with PatternNodes =>
 
   // debugging var, set to true to see how sausages are made
   private var trace = false
@@ -40,61 +46,22 @@ trait ParallelMatching extends ast.TreeDSL {
   import Types._
   import CODE._
 
-  type TreeFunction1 = Tree => Tree
-  type TreeFunction2 = (Tree, Tree) => Tree
-
   object Implicits {
     implicit def mkPattern(t: Tree) = Pattern(t)
   }
   import Implicits._
 
   def ifDebug(body: => Unit): Unit          = { if (settings.debug.value) body }
-  def DBG(msg: String): Unit                = { ifDebug(println(msg)) }
+  def DBG(msg: => String): Unit             = { ifDebug(println(msg)) }
   def TRACE(f: String, xs: Any*): Unit      = { if (trace) println(if (xs.isEmpty) f else f.format(xs : _*)) }
   def logAndReturn[T](s: String, x: T): T   = { log(s + x.toString) ; x }
   def traceAndReturn[T](s: String, x: T): T = { TRACE(s + x.toString) ; x }
 
-  /**
-   * Encapsulates a symbol being matched on.
-   *
-   * sym match { ... }
-   *
-   * results in Scrutinee(sym).
-   *
-   * Note that we only ever match on Symbols, not Trees: a temporary variable
-   * is created for any expressions being matched on.
-   */
-  case class Scrutinee(val sym: Symbol) {
-    import definitions._
-
-    // presenting a face of our symbol
-    def tpe       = sym.tpe
-    def pos       = sym.pos
-    def accessors = sym.caseFieldAccessors
-    def id        = ID(sym)   // attributed ident
-
-    // tests
-    def isDefined = sym ne NoSymbol
-    def isSimple  = tpe.isChar || tpe.isInt
-
-    // sequences
-    def seqType   = tpe.widen baseType SeqClass
-    def elemType  = tpe typeArgs 0  // can this happen? if (seqType == NoType) error("...")
-
-    // for propagating "unchecked" to synthetic vars
-    def flags: List[Long] = if (sym hasFlag Flags.TRANS_FLAG) List(Flags.TRANS_FLAG) else Nil
-
-    def assertIsSubtype(other: Type) = assert(isSubType(tpe, other), "problem "+tpe+" not <: "+other)
-    def casted(headType: Type)(implicit theOwner: Symbol) =
-      if (tpe =:= headType) this
-      else new Scrutinee(newVar(pos, headType, flags = flags))
-  }
-
+  def isRightIgnoring(t: Tree) = t.isRightIgnoring
   case class Pattern(tree: Tree) {
     import definitions._
     lazy val    sym = tree.symbol
     lazy val    tpe = tree.tpe
-    lazy val symtpe = sym.tpe
     lazy val prefix = tpe.prefix
     lazy val tpeIfHead  = stripped.tree match {
       case p @ (_:Ident | _:Select) => singleType(stripped.prefix, stripped.sym) //should be singleton object
@@ -114,6 +81,13 @@ trait ParallelMatching extends ast.TreeDSL {
     final def isDefault = isDefaultPattern(tree)
     final def isEquals  = cond(tpe) { case TypeRef(_, EqualsPatternClass, _) => true }
 
+    /* a Seq ending in _* */
+    final def isRightIgnoring = {
+      def isStar(t: Tree) = cond(unbind(t)) { case Star(q) => isDefaultPattern(q) }
+
+      cond(tree) { case ArrayValue(_, xs) if !xs.isEmpty => isStar(xs.last) }
+    }
+
     final def getAlternativeBranches: List[Tree] = {
       def get_BIND(pctx: TreeFunction1, p: Tree): List[Tree] = p match {
         case b @ Bind(n, p)   => get_BIND((x: Tree) => pctx(treeCopy.Bind(b, n, x) setType x.tpe), p)
@@ -142,573 +116,17 @@ trait ParallelMatching extends ast.TreeDSL {
       (sym ne null) && (sym != NoSymbol) && prefix.isStable && (head =:= singleType(prefix, sym))
   }
 
-  case class Patterns(scrut: Scrutinee, ps: List[Pattern]) {
-    private lazy val column = ps map (_.tree)
-    lazy val head = ps.head
-    lazy val tail = Patterns(scrut, ps.tail)
-    lazy val last = ps.last
-    lazy val headType = head.tpeIfHead
-    lazy val isCaseHead = headType.isCaseClass
-    lazy val dummies = if (isCaseHead) getDummies(headType.typeSymbol.caseFieldAccessors.length) else Nil
-    lazy val size = ps.length
-
-    def apply(i: Int): Tree = ps(i).tree
-    def zip() = column.zipWithIndex
-    def zip[T](ys: List[T]) = column zip ys
-
-    def isObjectTest(pat: Pattern)  = pat isObjectTest headType
-    def isObjectTest(pat: Tree)     = Pattern(pat) isObjectTest headType
-    // an unapply for which we don't need a type test
-    def isUnapplyHead = cond (head.tree) { case __UnApply(_,tpe,_)  => scrut.tpe <:< tpe }
-
-    def isSimpleSwitch: Boolean =
-      scrut.isSimple && ps.init.forall(_.isSimpleSwitchCandidate) &&
-      // TODO: This needs to also allow the case that the last is a compatible type pattern.
-      (last.isSimpleSwitchCandidate || last.isDefault)
-
-    def mkRule(rest: Rep)(implicit rep: RepFactory): RuleApplication =
-      logAndReturn("mkRule: ", head match {
-          case x if x.isEquals          => new MixEquals(this, rest)
-          case Pattern(x: ArrayValue)   => if (isRightIgnoring(x)) new MixSequenceStar(this, rest)
-                                           else new MixSequence(this, rest)
-          case _ if isSimpleSwitch      => new MixLiterals(this, rest)
-          case _ if isUnapplyHead       => new MixUnapply(this, rest)
-          case _                        => new MixTypes(this, rest)
-        }
-      )
-  }
-
-  /**
-   * Class encapsulating a guard expression in a pattern match:
-   *   case ... if(tree) => ...
-   */
-  case class Guard(tree: Tree) {
-    def isEmpty   = tree eq EmptyTree
-    def duplicate = Guard(tree.duplicate)
-    override def toString() = if (isEmpty) "" else " // if %s" format tree
-  }
-  val NoGuard = Guard(EmptyTree)
-
-  /** picks which rewrite rule to apply
-   *  @precondition: column does not contain alternatives (ensured by initRep)
-   */
-  def MixtureRule(scrut: Scrutinee, column: List[Tree], rest: Rep)(implicit rep: RepFactory): RuleApplication =
-    Patterns(scrut, column map Pattern) mkRule rest
-
-  sealed abstract class RuleApplication(rep: RepFactory) {
-    implicit def typer = rep.typer
-
-    def pats: Patterns
-    def rest: Rep
-    lazy val Patterns(scrut, patterns) = pats
-    lazy val head = pats.head
-    private lazy val sym = scrut.sym
-
-    def mkFail(xs: List[Row])(implicit theOwner: Symbol) =
-      rep.make(sym :: rest.temp, xs)
-    def mkNewRep(pre: List[Symbol], post: List[Symbol], rows: List[Row])(implicit theOwner: Symbol) =
-      rep.make(pre ::: sym :: post, rows)
-
-    /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */
-    def tree(implicit theOwner: Symbol, failTree: Tree): Tree
-  }
-
-  case class ErrorRule(implicit rep:RepFactory) extends RuleApplication(rep) {
-    def pats: Patterns = impossible
-    def rest: Rep = impossible
-    final def tree(implicit theOwner: Symbol, failTree: Tree) = failTree
-  }
-
-  /**  {case ... if guard => bx} else {guardedRest} */
-  case class VariableRule(subst: Bindings, guard: Guard, guardedRest: Rep, bx: Int)(implicit rep:RepFactory) extends RuleApplication(rep) {
-    def pats: Patterns = impossible
-    def rest: Rep = guardedRest
-
-    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
-      val body      = typer typed rep.requestBody(bx, subst)
-      def vdefs     = subst.targetParams
-      def typedElse = guardedRest.toTree
-      def typedIf   = typer typed (IF (guard.duplicate.tree) THEN body ELSE typedElse)
-
-      if (guard.isEmpty) body
-      else typer typed squeezedBlock(vdefs, typedIf)
-    }
-  }
-
-  /** mixture rule for literals
-   */
-  class MixLiterals(val pats: Patterns, val rest: Rep)(implicit rep:RepFactory) extends RuleApplication(rep) {
-    // e.g. (1,1) (1,3) (42,2) for column { case ..1.. => ;; case ..42..=> ;; case ..1.. => }
-    var defaultV: Set[Symbol] = emptySymbolSet
-    var defaultIndexSet = new BitSet(pats.size)
-
-    def insertDefault(tag: Int, vs: Traversable[Symbol]) {
-      defaultIndexSet += tag
-      defaultV = defaultV ++ vs
-    }
-
-    def haveDefault: Boolean    = !defaultIndexSet.isEmpty
-    def defaultRows: List[Row]  = defaultIndexSet.toList reverseMap grabRow
-
-    protected var tagIndices = IntMap.empty[List[Int]]
-    protected def grabRow(index: Int): Row = {
-      val r = rest.row(index)
-      if (defaultV.isEmpty) r
-      else r.insert2(Nil, pats(index).boundVariables, scrut.sym)  // get vars
-    }
-
-    /** inserts row indices using in to list of tagIndices */
-    protected def tagIndicesToReps(implicit theOwner: Symbol) : List[(Int, Rep)] =
-      tagIndices map { case (k, v) => (k, rep.make(rest.temp, v.reverseMap(grabRow) ::: defaultRows)) } toList
-
-    protected def defaultsToRep(implicit theOwner: Symbol) = rep.make(rest.temp, defaultRows)
-
-    protected def insertTagIndexPair(tag: Int, index: Int) =
-      tagIndices = tagIndices.update(tag, index :: tagIndices.getOrElse(tag, Nil))
-
-    /** returns
-     *  @return list of continuations,
-     *  @return variables bound to default continuation,
-     *  @return optionally, a default continuation
-     **/
-    def getTransition(implicit theOwner: Symbol): (List[(Int,Rep)], Set[Symbol], Option[Rep]) =
-      (tagIndicesToReps, defaultV, if (haveDefault) Some(defaultsToRep) else None)
-
-    val varMap: List[(Int, List[Symbol])] =
-      (for ((x, i) <- pats.zip) yield x.stripped match {
-        case p @ LIT(c: Int)          => insertTagIndexPair(c, i)           ; Some(c,       definedVars(x))
-        case p @ LIT(c: Char)         => insertTagIndexPair(c.toInt, i)     ; Some(c.toInt, definedVars(x))
-        case p if isDefaultPattern(p) => insertDefault(i, x.boundVariables) ; None
-      }) . flatMap(x => x) . reverse
-
-    // lazy
-    private def bindVars(Tag: Int, orig: Bindings): Bindings  = {
-      def myBindVars(rest:List[(Int,List[Symbol])], bnd: Bindings): Bindings  = rest match {
-        case Nil => bnd
-        case (Tag,vs)::xs => myBindVars(xs, bnd.add(vs, scrut.sym))
-        case (_,  vs)::xs => myBindVars(xs, bnd)
-      }
-      myBindVars(varMap, orig)
-    }
-
-    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
-      val (branches, defaultV, defaultRep) = this.getTransition // tag body pairs
-      val cases = for ((tag, r) <- branches) yield {
-        val r2 = rep.make(r.temp, r.row map (x => x rebind bindVars(tag, x.subst)))
-
-        CASE(Literal(tag)) ==> r2.toTree
-      }
-      lazy val ndefault         = defaultRep map (_.toTree) getOrElse (failTree)
-      lazy val casesWithDefault = cases ::: List(CASE(WILD(definitions.IntClass.tpe)) ==> ndefault)
-
-      cases match {
-        case CaseDef(lit,_,body) :: Nil   => IF (scrut.id ANY_== lit) THEN body ELSE ndefault
-        case _                            =>
-          val target: Tree = if (scrut.tpe.isChar) scrut.id DOT nme.toInt else scrut.id // chars to ints
-          target MATCH (casesWithDefault: _*)
-      }
-    }
-    override def toString = {
-      "MixLiterals {\n  pats: %s\n  varMap: %s\n}".format(
-        pats, varMap
-      )
-    }
-  }
-
-  /** mixture rule for unapply pattern
-   */
-  class MixUnapply(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory)
-  extends RuleApplication(rep) {
-    lazy val Strip(vs, ua @ UnApply(app @ Apply(fxn, _ :: applyTail), args)) = head.tree
-
-    object sameUnapplyCall {
-      def sameFunction(fn1: Tree) = fxn.symbol == fn1.symbol && (fxn equalsStructure fn1)
-      def unapply(t: Tree) = t match {
-        case UnApply(Apply(fn1, _), args) if sameFunction(fn1)  => Some(args)
-        case _                                                  => None
-      }
-    }
-
-    def newVarCapture(pos: Position, tpe: Type)(implicit theOwner: Symbol) =
-      newVar(pos, tpe, flags = scrut.flags)
-
-    /** returns (unapply-call, success-rep, optional fail-rep*/
-    final def getTransition(implicit theOwner: Symbol): Branch[UnapplyCall] = {
-      val unapplyRes  = newVarCapture(ua.pos, app.tpe)
-      val rhs         = Apply(fxn, scrut.id :: applyTail) setType unapplyRes.tpe
-      val zipped      = pats zip rest.row
-      val nrowsOther  = zipped.tail flatMap {
-        case (Stripped(sameUnapplyCall(_)), _)  => Nil
-        case (pat, r)                           => List(r insert pat)
-      }
-
-      def mkTransition(vdefs: List[Tree], ntemps: List[Symbol], nrows: List[Row]) =
-        Branch(
-          UnapplyCall(typedValDef(unapplyRes, rhs), vdefs),
-          mkNewRep(ntemps, rest.temp, nrows),
-          if (nrowsOther.isEmpty) None else Some(mkFail(nrowsOther))
-        )
-
-      // Second argument is number of dummies to prepend in the default case
-      def mkNewRows(sameFilter: (List[Tree]) => List[Tree], dum: Int) =
-        for ((pat @ Strip(vs, p), r) <- zipped) yield p match {
-          case sameUnapplyCall(args)  => r.insert2(sameFilter(args) ::: List(EmptyTree), vs, scrut.sym)
-          case _                      => r insert (getDummies(dum) ::: List(pat))
-        }
-      def mkGet(s: Symbol) = typedValDef(s, fn(ID(unapplyRes), nme.get))
-      def mkVar(tpe: Type) = newVarCapture(ua.pos, tpe)
-
-      import definitions.{ getProductArgs, productProj }
-      // 0 args => Boolean, 1 => Option[T], >1 => Option[? <: ProductN[T1,...,Tn]]
-      args.length match {
-        case 0  =>
-          mkTransition(Nil, Nil, mkNewRows((xs) => Nil, 0))
-
-        case 1 =>
-          val vsym  = mkVar(app.tpe typeArgs 0)
-          val nrows = mkNewRows(xs => List(xs.head), 1)
-          val vdef  = mkGet(vsym)
-
-          mkTransition(List(vdef), List(vsym), nrows)
-
-        case _ =>
-          val uresGet   = mkVar(app.tpe typeArgs 0)
-          val vdefHead  = mkGet(uresGet)
-          val ts        = getProductArgs(uresGet.tpe).get
-          // val ts        = analyzer.unapplyTypeListFromReturnType(uresGet.tpe)
-          val nrows     = mkNewRows(identity, ts.size)
-
-          val (vdefs: List[Tree], vsyms: List[Symbol]) = List.unzip(
-            for ((vtpe, i) <- ts.zip((1 to ts.size).toList)) yield {
-              val vchild  = mkVar(vtpe)
-              val accSym  = productProj(uresGet, i)
-              val rhs     = typer typed fn(ID(uresGet), accSym)
-
-              (typedValDef(vchild, rhs), vchild)
-            })
-
-          mkTransition(vdefHead :: vdefs, vsyms, nrows)
-      }
-    } /* def getTransition(...) */
-
-    final def tree(implicit theOwner: Symbol, failTree: Tree) = {
-      val Branch(UnapplyCall(uacall, vdefs), srep, frep) = this.getTransition
-      val succ = srep.toTree
-      val fail = frep map (_.toTree) getOrElse (failTree)
-      val cond =
-        if (uacall.symbol.tpe.isBoolean) typer typed ID(uacall.symbol)
-        else uacall.symbol IS_DEFINED
-
-      typer typed (squeezedBlock(
-        List(rep handleOuter uacall),
-        IF(cond) THEN squeezedBlock(vdefs, succ) ELSE fail
-      ))
-    }
-    override def toString = {
-      "MixUnapply {\n  pats: %s\n  ua: %s\n}".format(
-        pats, ua
-      )
-    }
-  }
-
-  /** handle sequence pattern and ArrayValue (but not star patterns)
-   */
-  sealed class MixSequence(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {
-    def compareOp                 = head.tpe member nme.lengthCompare  // symbol for length comparison
-
-    final def removeStar(xs: List[Tree]): List[Tree] =
-      xs.init ::: makeBind(xs.last.boundVariables, WILD(scrut.seqType)) :: Nil
-
-    protected def getSubPatterns(len: Int, x: Tree): Option[List[Tree]] = x match {
-      case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == len)   => Some(xs ::: List(EmptyTree))
-      case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length == len+1) => Some(removeStar(xs)) // (*)
-      case EmptyTree | Ident(nme.WILDCARD)                                       => Some(getDummies(len+1))
-      case _                                                                     => None
-    }
-
-    protected def makeSuccRep(vs: List[Symbol], tail: Symbol, nrows: List[Row])(implicit theOwner: Symbol) =
-      rep.make(vs ::: tail :: rest.temp, nrows)
-
-    /** True if x must be checked even if y failed to match after passing its length test
-      * (the conditional supplied by getCond)
-      */
-    protected def mustCheck(x:Tree, y:Tree): Boolean =
-      isDefaultPattern(x) || ((x, y) match {
-        case (av @ ArrayValue(_,xs), bv @ ArrayValue(_,ys)) =>
-          // if they are both right-ignoring, x must be more general if it has fewer literals - bug #889
-          if (isRightIgnoring(av) && isRightIgnoring(bv) && xs.length < ys.length) true
-          // otherwise, x is more general only if it is y plus a star
-          else isRightIgnoring(av) && !isRightIgnoring(bv) && xs.length == ys.length+1                   // see (*)
-        case _ =>
-          false
-      })
-
-    case class TransitionContext(f: TreeFunction2)
-
-    // context (to be used in IF), success and failure Rep
-    def getTransition(implicit theOwner: Symbol): Branch[TransitionContext] = {
-      scrut assertIsSubtype head.tpe   // scrut.tpe <:< column.head.tpe confirmed by assertion
-      val av @ ArrayValue(_, xs)  = head.tree
-      val ys                      = if (isRightIgnoring(av)) xs.init else xs
-      val vs                      = ys map (y => newVar(y.stripped.pos, scrut.elemType))
-      def scrutineeCopy           = scrut.id.duplicate
-
-      lazy val tail               = newVar(scrut.pos, scrut.seqType)
-      lazy val lastBinding        = typedValDef(tail, scrutineeCopy DROP ys.size)
-      def elemAt(i: Int)          = typer typed ((scrutineeCopy DOT (scrutineeCopy.tpe member nme.apply))(LIT(i)))
-
-      val bindings =
-        (vs.zipWithIndex map { case (v,i) => typedValDef(v, elemAt(i)) }) ::: List(lastBinding)
-
-      val (nrows, frows) = List.unzip(
-        for ((c, row) <- pats zip rest.row) yield getSubPatterns(ys.size, c) match {
-          case Some(ps) => (Some(row insert ps), if (mustCheck(c, av)) Some(row insert c) else None)
-          case None     => (None, Some(row insert c))
-        })
-
-      val succ = makeSuccRep(vs, tail, nrows.flatMap(x => x))
-      val fail = mkFail(frows flatMap (x => x))
-      def context = (thenp: Tree, elsep: Tree) =>
-        IF (getPrecondition(scrutineeCopy, xs.length)) THEN squeezedBlock(bindings, thenp) ELSE elsep
-
-      Branch(TransitionContext(context), succ, Some(fail))
-    }
-
-    protected def lengthCheck(tree: Tree, len: Int, op: TreeFunction2) =
-      typer typed op((tree.duplicate DOT compareOp)(LIT(len)), ZERO)
-
-    // precondition for matching: sequence is exactly length of arg
-    protected def getPrecondition(tree: Tree, lengthArg: Int) =
-      lengthCheck(tree, lengthArg, _ ANY_== _)
-
-    final def tree(implicit theOwner: Symbol, failTree: Tree) = {
-      val Branch(TransitionContext(context), succ, Some(fail)) = this.getTransition
-      context(succ.toTree, fail.toTree)
-    }
-  }
-
-  /** handle sequence pattern and ArrayValue with star patterns
-   */
-  final class MixSequenceStar(pats: Patterns, rest:Rep)(implicit rep:RepFactory) extends MixSequence(pats, rest) {
-    // in principle, we could optimize more, but variable binding gets complicated (@todo use finite state methods instead)
-    override def getSubPatterns(minlen:Int, x:Tree) = x match {
-      case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length   == minlen) =>  // Seq(p1,...,pN)
-        Some(xs ::: gen.mkNil :: EmptyTree :: Nil)
-      case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 == minlen) =>  // Seq(p1,...,pN,_*)
-        Some(                                   removeStar(xs) ::: EmptyTree :: Nil)
-      case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1  < minlen) =>  // Seq(p1..,pJ,_*)   J < N
-        Some(                                  getDummies(minlen + 1) ::: x :: Nil)
-      case EmptyTree | Ident(nme.WILDCARD)      =>
-        Some(                                  getDummies(minlen + 1          + 1))
-      case _                                    =>
-        None
-
-    }
-
-    override protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) =
-      mkNewRep(vs ::: List(tail), rest.temp, nrows)
-
-    // precondition for matching - sequence is at least length of (arg - 1)
-    // I believe the "- 1" is to remove the _* term.
-    override protected def getPrecondition(tree: Tree, lengthArg: Int) =
-      lengthCheck(tree, lengthArg - 1, _ ANY_>= _)
-  }
-
-
-  // @todo: equals test for same constant
-  class MixEquals(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {
-    /** condition (to be used in IF), success and failure Rep */
-    final def getTransition(implicit theOwner: Symbol): (Branch[Tree], Symbol) = {
-      val vlue = (head.tpe: @unchecked) match {
-        case TypeRef(_,_,List(SingleType(pre,sym))) => REF(pre, sym)
-        case TypeRef(_,_,List(PseudoType(o)))       => o.duplicate
-      }
-      assert(vlue.tpe ne null, "value tpe is null")
-      val vs        = head.boundVariables
-      val nsuccFst  = rest.row.head.insert2(List(EmptyTree), vs, scrut.sym)
-      val failLabel = theOwner.newLabel(scrut.pos, newName(scrut.pos, "failCont%")) // warning, untyped
-      val sx        = rep shortCut failLabel // register shortcut
-      val nsuccRow  = nsuccFst :: Row(getDummies( 1 /* scrutinee */ + rest.temp.length), NoBinding, NoGuard, sx) :: Nil
-
-      // todo: optimize if no guard, and no further tests
-      val nsucc = mkNewRep(Nil, rest.temp, nsuccRow)
-      val nfail = mkFail(List.map2(rest.row.tail, pats.tail.ps)(_ insert _))
-
-      (Branch(typer typed (scrut.id ANY_== vlue), nsucc, Some(nfail)), failLabel)
-    }
-
-    final def tree(implicit theOwner: Symbol, failTree: Tree) = {
-      val (Branch(cond, srep, Some(frep)), failLabel) = this.getTransition
-      val cond2 = typer typed (rep handleOuter cond)
-      val fail  = typer typed frep.toTree
-      failLabel setInfo MethodType(Nil, fail.tpe)
-
-      typer typed { IF (cond2) THEN srep.toTree ELSE LabelDef(failLabel, Nil, fail) }
-    }
-  }
-
-  /** mixture rule for type tests
-  **/
-  class MixTypes(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {
-    private def subpatterns(p: Tree): List[Tree] = p match {
-      case Bind(_, p)                                                 => subpatterns(p)
-      case app @ Apply(fn, ps) if app.tpe.isCaseClass && fn.isType    => if (pats.isCaseHead) ps else pats.dummies
-      case Apply(fn, xs) if !xs.isEmpty || fn.isType                  => abort("strange Apply")
-      case _                                                          => pats.dummies
-    }
-
-    // moreSpecific: more specific patterns
-    //     subsumed: more general patterns (subsuming current), row index and subpatterns
-    //    remaining: remaining, row index and pattern
-    def join[T](xs: List[Option[T]]): List[T] = xs.flatMap(x => x)
-    val (moreSpecific, subsumed, remaining) : (List[Tree], List[(Int, List[Tree])], List[(Int, Tree)]) = unzip3(
-      for ((pat @ Stripped(spat), j) <- pats.zip) yield {
-        def eqHead(tpe: Type)         = pats.headType =:= tpe
-        def alts(yes: Tree, no: Tree) = if (eqHead(pat.tpe)) yes else no
-
-        lazy val isDef                = isDefaultPattern(pat)
-        lazy val cmp: TypeComparison  = spat.tpe cmp pats.headType  // contains type info about pattern's type vs. head pattern
-        lazy val dummy                = (j, pats.dummies)
-        lazy val pass                 = (j, pat)
-        lazy val subs                 = (j, subpatterns(pat))
-
-        import cmp._  // imports xIsaY, etc.
-
-        // each pattern will yield a triple of options corresponding to the three lists,
-        // which will be flattened down to the values
-        implicit def mkOpt[T](x: T): Option[T] = Some(x)    // limits noise from Some(value)
-        (spat match {
-          case LIT(null) if !eqHead(spat.tpe)               => (None, None, pass)           // special case for constant null
-          case _ if pats.isObjectTest(pat)                  => (EmptyTree, dummy, None)     // matching an object
-          case Typed(p @ Stripped(_: UnApply), _) if xIsaY  => (p, dummy, None)             // <:< is never <equals>
-          case q @ Typed(pp, _) if xIsaY                    => (alts(pp, q), dummy, None)   // never =:= for <equals>
-          // this next line inflicted great suffering upon innocents
-          // case z: UnApply                                   => (None, None, pass)
-          // XXX note - while removing the above line fixed the abhorrent "wrong answer" behavior
-          // illustrated in bug #1697, it then led to "consistency problem in target generation"
-          // failures with extractors in the first position (see classifyPat.)
-          case z: UnApply                                   => (EmptyTree, dummy, pass)
-          case _ if erased.xIsaY || xIsaY && !isDef         => (alts(EmptyTree, pat), subs, None) // never =:= for <equals>
-          case _ if erased.yIsaX || yIsaX || isDef          => (EmptyTree, dummy, pass)     // subsuming (matched *and* remaining pattern)
-          case _                                            => (None, None, pass)
-        }) : (Option[Tree], Option[(Int, List[Tree])], Option[(Int, Tree)])
-      }
-    ) match { case (x,y,z) => (join(x), join(y), join(z)) }
-
-    override def toString = {
-      "MixTypes(%s: %s) {\n  moreSpecific: %s\n  subsumed: %s\n  remaining: %s\n}".format(
-        scrut, scrut.tpe, moreSpecific, subsumed, remaining
-      )
-    }
-
-    /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */
-    final def getTransition(implicit theOwner: Symbol): Branch[Scrutinee] = {
-      val casted = scrut casted pats.headType
-
-      // succeeding => transition to translate(subsumed) (taking into account more specific)
-      val nmatrix = {
-        val ms = moreSpecific exists (_ != EmptyTree)
-        val accessorTemps =
-          if (!pats.isCaseHead) Nil
-          else casted.accessors map (meth => newVar(scrut.pos, (casted.tpe memberType meth).resultType, scrut.flags))
-        val subtestTemps = if (!ms) Nil else List(casted.sym)
-        val subtests =
-          if (!ms) subsumed
-          else moreSpecific.zip(subsumed) map { case (mspat, (j, pats)) => (j, mspat::pats) }
-        val ntriples =
-          for ((j, ps) <- subtests ; val Strip(vs, thePat) = pats(j)) yield
-            (rest row j).insert2(ps, vs, casted.sym)
-
-        rep.make(subtestTemps ::: accessorTemps ::: rest.temp, ntriples)
-      }
-
-      // fails      => transition to translate(remaining)
-      val nmatrixFail: Option[Rep] = {
-        val ntriples = for ((j, pat) <- remaining) yield (rest row j) insert pat
-        if (ntriples.isEmpty) None else Some(mkFail(ntriples))
-      }
-
-      Branch(casted, nmatrix, nmatrixFail)
-    }
-
-    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
-      val Branch(casted, srep, frep) = this.getTransition
-      val cond = condition(casted.tpe, scrut)
-      val succ = srep.toTree
-      val fail = frep map (_.toTree) getOrElse (failTree)
-
-      // dig out case field accessors that were buried in (***)
-      val cfa       = if (!pats.isCaseHead) Nil else casted.accessors
-      val caseTemps = srep.temp match { case x :: xs if x == casted.sym => xs ; case x => x }
-      def needCast  = if (casted.sym ne scrut.sym) List(VAL(casted.sym) === (scrut.id AS_ANY casted.tpe)) else Nil
-      val vdefs     = needCast ::: (
-        for ((tmp, accessor) <- caseTemps zip cfa) yield
-          typedValDef(tmp, typer typed fn(casted.id, accessor))
-      )
-
-      typer typed (IF (cond) THEN squeezedBlock(vdefs, succ) ELSE fail)
-    }
-  }
-
-  case class Row(pat: List[Tree], subst: Bindings, guard: Guard, bx: Int) {
-    def insert(h: Tree)                               = copy(pat = h :: pat)
-    def insert(hs: List[Tree])                        = copy(pat = hs ::: pat)    // prepends supplied tree
-    def replace(hs: List[Tree])                       = copy(pat = hs)            // substitutes for patterns
-    def rebind(b: Bindings)                           = copy(subst = b)           // substitutes for bindings
-    def insert2(hs: List[Tree], vs: Iterable[Symbol], temp: Symbol) =             // prepends and prepends
-      copy(pat = hs ::: pat, subst = subst.add(vs, temp))
-
-    def insert(p: Pattern)                            = copy(pat = p.tree :: pat) // transitioning to patterns
-
-    /** returns true if the patterns in this row cover a type symbols "combination" and there is no guard
-     *  @param comb pairs of (column index, type symbol)
-     */
-    def covers(comb: List[Combo]) = {
-      val results = for (Combo(i, sym) <- comb ; val p = pat(i).stripped) yield p match {
-        case _ if isDefaultPattern(p)   => true
-        case _: UnApply | _: ArrayValue => true
-        case _                          => p.tpe coversSym sym
-      }
-
-      guard.isEmpty && (results forall (true ==))
-    }
-
-    // returns this row with alternatives expanded
-    def expand(classifyPat: (Tree, Int) => Tree): List[Row] = {
-      def isAlternative(p: Tree) = cond(p.stripped) { case Alternative(_) => true }
-      def getAlternativeBranches(p: Tree): List[Tree] = {
-        def get_BIND(pctx: TreeFunction1, p:Tree): List[Tree] = p match {
-          case b @ Bind(n,p)   => get_BIND((x: Tree) => pctx(treeCopy.Bind(b, n, x) setType x.tpe), p)
-          case Alternative(ps) => ps map pctx
-        }
-        logAndReturn("get_BIND: ", get_BIND(x => x, p))
-      }
-
-      val indexOfAlternative            = pat findIndexOf isAlternative
-      val pats: List[Tree]              = List.map2(pat, pat.indices.toList)(classifyPat)
-      lazy val (prefix, alts :: suffix) = pats splitAt indexOfAlternative
-      lazy val alternativeBranches      = getAlternativeBranches(alts) map (x => replace(prefix ::: x :: suffix))
-
-      if (indexOfAlternative == -1) List(replace(pats)) else alternativeBranches
-    }
-    override def toString() = {
-      val patStr = pat.mkString
-      val others = List(subst, guard) map (_.toString) filter (_ != "")
-      val otherStr = if (others.isEmpty) "" else " // " + others.mkString(" ")
-
-      "Row(%d) %s%s".format(bx, patStr, otherStr)
-    }
-  }
-
   import collection.mutable.HashMap
-  class RepFactory(val handleOuter: TreeFunction1, val typer: Typer) {
+  class MatchMatrix(context: MatchMatrixContext, failTree: Tree) {
+    import context._
+
     var vss: List[List[Symbol]] = _
     val labels: HashMap[Int, Symbol] = new HashMap
     var targets: List[Tree] = _
     var reached: BitSet = _
     var shortCuts: List[Symbol] = _
 
-    final def make(temp: List[Symbol], row:List[Row], targets: List[Tree], vss: List[List[Symbol]])(implicit theOwner: Symbol): Rep = {
+    final def make(temp: List[Symbol], row:List[Row], targets: List[Tree], vss: List[List[Symbol]]): Rep = {
       // ensured that labels(i) eq null for all i, cleanup() has to be called after translation
       this.vss          = vss
       this.labels.clear()
@@ -724,7 +142,7 @@ trait ParallelMatching extends ast.TreeDSL {
       -shortCuts.length
     }
 
-    final def cleanup(tree: Tree)(implicit theOwner: Symbol): Tree = {
+    final def cleanup(tree: Tree): Tree = {
       // Extractors which can spot pure true/false expressions
       // even through the haze of braces
       abstract class SeeThroughBlocks[T] {
@@ -792,7 +210,7 @@ trait ParallelMatching extends ast.TreeDSL {
     /** 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)(implicit theOwner: Symbol): Tree = {
+    final def requestBody(bx: Int, subst: Bindings): Tree = {
       if (bx < 0) { // is shortcut
         val jlabel = shortCuts(-bx-1)
         return Apply(ID(jlabel), Nil)
@@ -801,15 +219,14 @@ trait ParallelMatching extends ast.TreeDSL {
         // might be bound elsewhere
         val (vsyms, vdefs) : (List[Symbol], List[Tree]) = List.unzip(
           for (v <- vss(bx) ; substv <- subst(v)) yield
-            (v, typedValDef(v, substv)(typer))
+            (v, typedValDef(v, substv))
         )
 
         val body    = targets(bx)
         // @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 label   = theOwner.newLabel(body.pos, "body%"+bx) setInfo MethodType(vsyms, tpe)
         val newType = MethodType(vsyms, tpe)
-        val label   = theOwner.newLabel(body.pos, "body%"+bx) setInfo newType
+        val label   = owner.newLabel(body.pos, "body%"+bx) setInfo newType
         labels(bx)  = label
 
         return logAndReturn("requestBody(%d) first time: ".format(bx), squeezedBlock(vdefs, (
@@ -848,14 +265,14 @@ trait ParallelMatching extends ast.TreeDSL {
         cunit.error(body.pos, msg)
       }
 
-      def vds = for (v <- vss(bx) ; substv <- subst(v)) yield typedValDef(v, substv)(typer)
+      def vds = for (v <- vss(bx) ; substv <- subst(v)) yield typedValDef(v, substv)
 
       if (isLabellable(body)) ID(label) APPLY (args)
       else                    squeezedBlock(vds, body.duplicate setType resultType)
     }
 
     /** the injection here handles alternatives and unapply type tests */
-    final def make(temp: List[Symbol], row1: List[Row])(implicit theOwner: Symbol): Rep = {
+    final def make(temp: List[Symbol], row1: List[Row]): Rep = {
       // equals check: call singleType(NoPrefix, o.symbol) `stpe'. Then we could also return
       // `typeRef(definitions.ScalaPackageClass.tpe, definitions.EqualsPatternClass, List(stpe))'
       // and force an equality check. However, exhaustivity checking would not work anymore.
@@ -954,215 +371,822 @@ trait ParallelMatching extends ast.TreeDSL {
         ) filterNot (_._2.isEmpty)
       val strs = toPrint map { case (k, v) => "    %s = %s\n".format(k, v) }
 
-      if (toPrint.isEmpty) "RepFactory()"
-      else "RepFactory(\n%s)".format(strs mkString)
+      if (toPrint.isEmpty) "MatchMatrix()"
+      else "MatchMatrix(\n%s)".format(strs mkString)
+    }
+
+    /**
+     * Encapsulates a symbol being matched on.
+     *
+     * sym match { ... }
+     *
+     * results in Scrutinee(sym).
+     *
+     * Note that we only ever match on Symbols, not Trees: a temporary variable
+     * is created for any expressions being matched on.
+     */
+    case class Scrutinee(val sym: Symbol) {
+      import definitions._
+
+      // presenting a face of our symbol
+      def tpe       = sym.tpe
+      def pos       = sym.pos
+      def accessors = sym.caseFieldAccessors
+      def id        = ID(sym)   // attributed ident
+
+      // tests
+      def isDefined = sym ne NoSymbol
+      def isSimple  = tpe.isChar || tpe.isInt
+
+      // sequences
+      def seqType   = tpe.widen baseType SeqClass
+      def elemType  = tpe typeArgs 0  // can this happen? if (seqType == NoType) error("...")
+
+      // for propagating "unchecked" to synthetic vars
+      def flags: List[Long] = List(Flags.TRANS_FLAG) filter (sym hasFlag _)
+
+      def assertIsSubtype(other: Type) = assert(isSubType(tpe, other), "problem "+tpe+" not <: "+other)
+      def casted(headType: Type) =
+        if (tpe =:= headType) this
+        else new Scrutinee(newVar(pos, headType, flags = flags))
     }
-  }
 
-  case class Combo(index: Int, sym: Symbol) {}
-  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])
+    case class Patterns(scrut: Scrutinee, ps: List[Pattern]) {
+      private lazy val column = ps map (_.tree)
+      lazy val head = ps.head
+      lazy val tail = Patterns(scrut, ps.tail)
+      lazy val last = ps.last
+      lazy val headType = head.tpeIfHead
+      lazy val isCaseHead = headType.isCaseClass
+      lazy val dummies = if (isCaseHead) getDummies(headType.typeSymbol.caseFieldAccessors.length) else Nil
+      lazy val size = ps.length
+
+      def apply(i: Int): Tree = ps(i).tree
+      def zip() = column.zipWithIndex
+      def zip[T](ys: List[T]) = column zip ys
+
+      def isObjectTest(pat: Pattern)  = pat isObjectTest headType
+      def isObjectTest(pat: Tree)     = Pattern(pat) isObjectTest headType
+      // an unapply for which we don't need a type test
+      def isUnapplyHead = cond (head.tree) { case __UnApply(_,tpe,_)  => scrut.tpe <:< tpe }
+
+      def isSimpleSwitch: Boolean =
+        scrut.isSimple && ps.init.forall(_.isSimpleSwitchCandidate) &&
+        // TODO: This needs to also allow the case that the last is a compatible type pattern.
+        (last.isSimpleSwitchCandidate || last.isDefault)
+
+      def mkRule(rest: Rep): RuleApplication =
+        logAndReturn("mkRule: ", head match {
+            case x if x.isEquals          => new MixEquals(this, rest)
+            case Pattern(x: ArrayValue)   => if (x.isRightIgnoring) new MixSequenceStar(this, rest)
+                                             else new MixSequence(this, rest)
+            case _ if isSimpleSwitch      => new MixLiterals(this, rest)
+            case _ if isUnapplyHead       => new MixUnapply(this, rest)
+            case _                        => new MixTypes(this, rest)
+          }
+        )
+    }
 
-  case class Rep(val temp: List[Symbol], val row: List[Row]) {
-    /** converts this to a tree - performs recursive call to translation in the process to get sub reps
+    /**
+     * Class encapsulating a guard expression in a pattern match:
+     *   case ... if(tree) => ...
      */
-    final def toTree(implicit theOwner: Symbol, failTree: Tree, rep: RepFactory): Tree =
-      this.applyRule.tree
-
-    private def toUse(s: Symbol) =
-       (s hasFlag Flags.MUTABLE) &&                 // indicates that have not yet checked exhaustivity
-      !(s hasFlag Flags.TRANS_FLAG) &&              // indicates @unchecked
-       (s.tpe.typeSymbol hasFlag Flags.SEALED)
-
-    // the superclass is taken if it is not abstract
-    private def countSuper(s: Symbol): Set[Symbol]  = if (s hasFlag Flags.ABSTRACT) emptySymbolSet else Set(s)
-    private def countSymbol(s: Symbol): Set[Symbol] = candidates(s) ++ countSuper(s)
-    private def candidates(s: Symbol): Set[Symbol]  =
-      if (s hasFlag Flags.SEALED) s.children flatMap countSymbol
-      else emptySymbolSet
-
-    private def setsToCombine: List[(Int, Set[Symbol])] =
-      for ((sym, i) <- temp.zipWithIndex ; if toUse(sym)) yield {
-        sym resetFlag Flags.MUTABLE
-        (i, candidates(sym.tpe.typeSymbol))
-      }
+    case class Guard(tree: Tree) {
+      def isEmpty   = tree eq EmptyTree
+      def duplicate = Guard(tree.duplicate)
+      override def toString() = if (isEmpty) "" else " // if %s" format tree
+    }
+    val NoGuard = Guard(EmptyTree)
+
+    /** "The Mixture Rule"
+
+          {v=pat1, pats1 .. } {q1}
+    match {..               } {..}
+          {v=patn, patsn .. } {qn}
+
+    The is the real work-horse of the algorithm. There is some column whose top-most pattern is a
+    constructor. (Forsimplicity, itisdepicted above asthe left-most column, but anycolumn will do.)
+    The goal is to build a test state with the variablevand some outgoing arcs (one for each construc-
+    tor and possibly a default arc). Foreach constructorcin the selected column, its arc is defined as
+    follows:
+
+    Let {i1,...,ij} be the row-indices of the patterns in the column that matchc. Since the pat-
+    terns are viewed as regular expressions, this will be the indices of the patterns that either
+    have the same constructor c, or are wildcards.
+
+    Let {pat1,...,patj} be the patterns in the column corresponding to the indices computed
+    above, and let nbe the arity of the constructor c, i.e. the number of sub-patterns it has. For
+    eachpati, its n sub-patterns are extracted; if pat i is a wildcard, nwildcards are produced
+    instead, each tagged with the right path variable. This results in a pattern matrix with n
+    columns and j rows. This matrix is then appended to the result of selecting, from each col-
+    umn in the rest of the original matrix, those rows whose indices are in {i1,...,ij}. Finally
+    the indices are used to select the corresponding final states that go with these rows. Note
+    that the order of the indices is significant; selected rows do not change their relative orders.
+    The arc for the constructor c is now defined as (c’,state), where c’ is cwith any
+    immediate sub-patterns replaced by their path variables (thus c’ is a simple pattern), and
+    state is the result of recursively applying match to the new matrix and the new sequence
+    of final states.
+
+    Finally, the possibility for matching failure is considered. If the set of constructors is exhaustive,
+    then no more arcs are computed. Otherwise, a default arc(_,state)is the last arc. If there are
+    any wildcard patterns in the selected column, then their rows are selected from the rest of the
+    matrix and the final states, and the state is the result of applying match to the new matrix and
+    states. Otherwise,the error state is used after its reference count has been incremented.
+    **/
+
+    /** picks which rewrite rule to apply
+     *  @precondition: column does not contain alternatives (ensured by initRep)
+     */
+    def MixtureRule(scrut: Scrutinee, column: List[Tree], rest: Rep): RuleApplication =
+      Patterns(scrut, column map Pattern) mkRule rest
+
+    sealed abstract class RuleApplication {
+      def pats: Patterns
+      def rest: Rep
+      lazy val Patterns(scrut, patterns) = pats
+      lazy val head = pats.head
+      private lazy val sym = scrut.sym
+
+      def mkFail(xs: List[Row]) =
+        make(sym :: rest.temp, xs)
+      def mkNewRep(pre: List[Symbol], post: List[Symbol], rows: List[Row]) =
+        make(pre ::: sym :: post, rows)
+
+      /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */
+      def tree(): Tree
+    }
+
+    case class ErrorRule() extends RuleApplication {
+      def pats: Patterns = impossible
+      def rest: Rep = impossible
+      final def tree() = failTree
+    }
+
+    /** {case ... if guard => bx} else {guardedRest} */
+    /** VariableRule: The top-most row has only variable (non-constructor) patterns. */
+    case class VariableRule(subst: Bindings, guard: Guard, guardedRest: Rep, bx: Int) extends RuleApplication {
+      def pats: Patterns = impossible
+      def rest: Rep = guardedRest
 
-    // computes cartesian product, keeps indices available
-    private def combine(colcom: List[(Int, Set[Symbol])]): List[List[Combo]] = colcom match {
-      case Nil              => Nil
-      case (i, syms) :: Nil => syms.toList map (s => List(Combo(i, s)))
-      case (i, syms) :: cs  => for (s <- syms.toList; rest <- combine(cs)) yield Combo(i, s) :: rest
+      final def tree(): Tree = {
+        def body      = requestBody(bx, subst)
+        def guardTest = IF (guard.duplicate.tree) THEN body ELSE guardedRest.toTree
+
+        typer typed(
+          if (guard.isEmpty) body
+          else squeezedBlock(subst.targetParams(typer), guardTest)
+        )
+      }
     }
 
-    private def comboCovers(combo: List[Combo]) = row exists (_ covers combo)
+    /** mixture rule for literals
+     */
+    class MixLiterals(val pats: Patterns, val rest: Rep) extends RuleApplication {
+      // e.g. (1,1) (1,3) (42,2) for column { case ..1.. => ;; case ..42..=> ;; case ..1.. => }
+      var defaultV: Set[Symbol] = emptySymbolSet
+      var defaultIndexSet = new BitSet(pats.size)
+
+      def insertDefault(tag: Int, vs: Traversable[Symbol]) {
+        defaultIndexSet += tag
+        defaultV = defaultV ++ vs
+      }
+
+      def haveDefault: Boolean    = !defaultIndexSet.isEmpty
+      def defaultRows: List[Row]  = defaultIndexSet.toList reverseMap grabRow
 
-    def init: this.type = {
-      val allcomb = combine(setsToCombine)
-      if (allcomb forall comboCovers) return this
+      protected var tagIndices = IntMap.empty[List[Int]]
+      protected def grabRow(index: Int): Row = {
+        val r = rest.row(index)
+        if (defaultV.isEmpty) r
+        else r.insert2(Nil, pats(index).boundVariables, scrut.sym)  // get vars
+      }
 
-      // if we reach here, patterns were not exhaustive
-      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)
+      /** inserts row indices using in to list of tagIndices */
+      protected def tagIndicesToReps() : List[(Int, Rep)] =
+        tagIndices map { case (k, v) => (k, make(rest.temp, (v reverseMap grabRow) ::: defaultRows)) } toList
+
+      protected def defaultsToRep() = make(rest.temp, defaultRows)
+
+      protected def insertTagIndexPair(tag: Int, index: Int) =
+        tagIndices = tagIndices.update(tag, index :: tagIndices.getOrElse(tag, Nil))
+
+      /** returns
+       *  @return list of continuations,
+       *  @return variables bound to default continuation,
+       *  @return optionally, a default continuation
+       **/
+      def getTransition(): (List[(Int,Rep)], Set[Symbol], Option[Rep]) =
+        (tagIndicesToReps, defaultV, if (haveDefault) Some(defaultsToRep) else None)
+
+      val varMap: List[(Int, List[Symbol])] =
+        (for ((x, i) <- pats.zip) yield x.stripped match {
+          case p @ LIT(c: Int)          => insertTagIndexPair(c, i)           ; Some(c,       definedVars(x))
+          case p @ LIT(c: Char)         => insertTagIndexPair(c.toInt, i)     ; Some(c.toInt, definedVars(x))
+          case p if isDefaultPattern(p) => insertDefault(i, x.boundVariables) ; None
+        }) flatMap (x => x) reverse
+
+      // lazy
+      private def bindVars(Tag: Int, orig: Bindings): Bindings = {
+        def myBindVars(rest:List[(Int,List[Symbol])], bnd: Bindings): Bindings = rest match {
+          case Nil => bnd
+          case (Tag,vs)::xs => myBindVars(xs, bnd.add(vs, scrut.sym))
+          case (_,  vs)::xs => myBindVars(xs, bnd)
+        }
+        myBindVars(varMap, orig)
       }
-      def mkMissingStr(open: List[Combo]) =
-        "missing combination " + temp.indices.map(mkPad(open, _)).mkString + "\n"
 
-      val missingCombos = (allcomb filter (open => row.forall(!_.covers(open))) map mkMissingStr).mkString
-      cunit.warning(temp.head.pos, "match is not exhaustive!\n" + missingCombos)
-      this
+      final def tree(): Tree = {
+        val (branches, defaultV, defaultRep) = this.getTransition // tag body pairs
+        val cases = for ((tag, r) <- branches) yield {
+          val r2 = make(r.temp, r.row map (x => x rebind bindVars(tag, x.subst)))
+
+          CASE(Literal(tag)) ==> r2.toTree
+        }
+        lazy val ndefault         = defaultRep map (_.toTree) getOrElse (failTree)
+        lazy val casesWithDefault = cases ::: List(CASE(WILD(definitions.IntClass.tpe)) ==> ndefault)
+
+        cases match {
+          case CaseDef(lit,_,body) :: Nil   => IF (scrut.id ANY_== lit) THEN body ELSE ndefault
+          case _                            =>
+            val target: Tree = if (scrut.tpe.isChar) scrut.id DOT nme.toInt else scrut.id // chars to ints
+            target MATCH (casesWithDefault: _*)
+        }
+      }
+      override def toString = {
+        "MixLiterals {\n  pats: %s\n  varMap: %s\n}".format(
+          pats, varMap
+        )
+      }
     }
 
-    /*   internal representation is (temp:List[Symbol], row:List[Row])
-     *
-     *         tmp1       tmp_m
+    /** mixture rule for unapply pattern
      */
-    final def applyRule(implicit theOwner: Symbol, rep: RepFactory): RuleApplication = {
-      def dropIndex[T](xs: List[T], n: Int) = (xs take n) ::: (xs drop (n + 1))
-      row match {
-        case Nil                              => ErrorRule()
-        case Row(pats, subst, g, bx) :: xs    =>
-
-          var bnd = subst
-          for (((rpat, t), px) <- pats zip temp zipWithIndex) {
-            val Strip(vs, p) = rpat
-
-            if (isDefaultPattern(p)) bnd = bnd.add(vs, t)
-            else {
-              // Row( _  ... _ p_1i  ...  p_1n   g_m  b_m ) :: rows
-              // cut out column px that contains the non-default pattern
-              val column    = rpat :: (row.tail map (_ pat px))
-              val restTemp  = dropIndex(temp, px)
-              val restRows  = row map (r => r replace dropIndex(r.pat, px))
-              val mr        = MixtureRule(new Scrutinee(t), column, rep.make(restTemp, restRows))
-
-              // TRACE("Mixture rule is = " + mr.getClass)
-              return mr
-            }
+    class MixUnapply(val pats: Patterns, val rest: Rep) extends RuleApplication {
+      lazy val Strip(vs, ua @ UnApply(app @ Apply(fxn, _ :: applyTail), args)) = head.tree
+
+      object sameUnapplyCall {
+        def sameFunction(fn1: Tree) = fxn.symbol == fn1.symbol && (fxn equalsStructure fn1)
+        def unapply(t: Tree) = t match {
+          case UnApply(Apply(fn1, _), args) if sameFunction(fn1)  => Some(args)
+          case _                                                  => None
+        }
+      }
+
+      def newVarCapture(pos: Position, tpe: Type) =
+        newVar(pos, tpe, flags = scrut.flags)
+
+      /** returns (unapply-call, success-rep, optional fail-rep*/
+      final def getTransition(): Branch[UnapplyCall] = {
+        val unapplyRes  = newVarCapture(ua.pos, app.tpe)
+        val rhs         = Apply(fxn, scrut.id :: applyTail) setType unapplyRes.tpe
+        val zipped      = pats zip rest.row
+        val nrowsOther  = zipped.tail flatMap {
+          case (Stripped(sameUnapplyCall(_)), _)  => Nil
+          case (pat, r)                           => List(r insert pat)
+        }
+
+        def mkTransition(vdefs: List[Tree], ntemps: List[Symbol], nrows: List[Row]) =
+          Branch(
+            UnapplyCall(typedValDef(unapplyRes, rhs), vdefs),
+            mkNewRep(ntemps, rest.temp, nrows),
+            if (nrowsOther.isEmpty) None else Some(mkFail(nrowsOther))
+          )
+
+        // Second argument is number of dummies to prepend in the default case
+        def mkNewRows(sameFilter: (List[Tree]) => List[Tree], dum: Int) =
+          for ((pat @ Strip(vs, p), r) <- zipped) yield p match {
+            case sameUnapplyCall(args)  => r.insert2(sameFilter(args) ::: List(EmptyTree), vs, scrut.sym)
+            case _                      => r insert (getDummies(dum) ::: List(pat))
           }
-          // Row(   _   ...   _     g_1  b_1 ) :: rows     it's all default patterns
-          val rest = if (g.isEmpty) null else rep.make(temp, xs)    // TODO - why null?
-          VariableRule (bnd, g, rest, bx)
+        def mkGet(s: Symbol) = typedValDef(s, fn(ID(unapplyRes), nme.get))
+        def mkVar(tpe: Type) = newVarCapture(ua.pos, tpe)
+
+        import definitions.{ getProductArgs, productProj }
+        // 0 args => Boolean, 1 => Option[T], >1 => Option[? <: ProductN[T1,...,Tn]]
+        args.length match {
+          case 0  =>
+            mkTransition(Nil, Nil, mkNewRows((xs) => Nil, 0))
+
+          case 1 =>
+            val vsym  = mkVar(app.tpe typeArgs 0)
+            val nrows = mkNewRows(xs => List(xs.head), 1)
+            val vdef  = mkGet(vsym)
+
+            mkTransition(List(vdef), List(vsym), nrows)
+
+          case _ =>
+            val uresGet   = mkVar(app.tpe typeArgs 0)
+            val vdefHead  = mkGet(uresGet)
+            val ts        = getProductArgs(uresGet.tpe).get
+            val nrows     = mkNewRows(identity, ts.size)
+
+            val (vdefs: List[Tree], vsyms: List[Symbol]) = List.unzip(
+              for ((vtpe, i) <- ts.zip((1 to ts.size).toList)) yield {
+                val vchild  = mkVar(vtpe)
+                val accSym  = productProj(uresGet, i)
+                val rhs     = typer typed fn(ID(uresGet), accSym)
+
+                (typedValDef(vchild, rhs), vchild)
+              })
+
+            mkTransition(vdefHead :: vdefs, vsyms, nrows)
+        }
+      } /* def getTransition(...) */
+
+      final def tree() = {
+        val Branch(UnapplyCall(uacall, vdefs), srep, frep) = this.getTransition
+        val succ = srep.toTree
+        val fail = frep map (_.toTree) getOrElse (failTree)
+        val cond =
+          if (uacall.symbol.tpe.isBoolean) ID(uacall.symbol)
+          else uacall.symbol IS_DEFINED
+
+        typer typed squeezedBlock(
+          List(handleOuter(uacall)),
+          IF (cond) THEN squeezedBlock(vdefs, succ) ELSE fail
+        )
+      }
+      override def toString = {
+        "MixUnapply {\n  pats: %s\n  ua: %s\n}".format(
+          pats, ua
+        )
       }
     }
 
-    // a fancy toString method for debugging
-    override def toString() = {
-      val tempStr = (temp map (t => pad(t.name))).mkString
-      val underlines = tempStr.replaceAll("""\S""", "-")
-      val rowStr = (
-        for (Row(pat, subst, guard, bx) <- row) yield {
-          val extraStr: String = guard.toString + subst
-          "%s %s\n".format(pat map pad mkString, extraStr)
+    /** handle sequence pattern and ArrayValue (but not star patterns)
+     */
+    sealed class MixSequence(val pats: Patterns, val rest: Rep) extends RuleApplication {
+
+      final def removeStar(xs: List[Tree]): List[Tree] =
+        xs.init ::: makeBind(xs.last.boundVariables, WILD(scrut.seqType)) :: Nil
+
+      protected def getSubPatterns(len: Int, x: Tree): Option[List[Tree]] = x match {
+        case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == len)   => Some(xs ::: List(EmptyTree))
+        case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length == len+1) => Some(removeStar(xs)) // (*)
+        case EmptyTree | Ident(nme.WILDCARD)                                       => Some(getDummies(len+1))
+        case _                                                                     => None
+      }
+
+      protected def makeSuccRep(vs: List[Symbol], tail: Symbol, nrows: List[Row]) =
+        make(vs ::: tail :: rest.temp, nrows)
+
+      /** True if x must be checked even if y failed to match after passing its length test
+        * (the conditional supplied by getPrecondition)
+        */
+      protected def mustCheck(x:Tree, y:Tree): Boolean =
+        isDefaultPattern(x) || cond((x, y)) {
+          case (av @ ArrayValue(_, xs), bv @ ArrayValue(_, ys)) if isRightIgnoring(av)  =>
+            ( isRightIgnoring(bv) && xs.length <  ys.length    ) ||   // see bug #889
+            (!isRightIgnoring(bv) && xs.length == ys.length + 1)
         }
-      ) mkString
 
-      if (temp.size == 0) "Rep(%dx%d)".format(temp.size, row.size)
-      else "Rep(%dx%d)\n%s\n%s\n%s".format(temp.size, row.size, tempStr, underlines, rowStr)
+      case class TransitionContext(f: TreeFunction2)
+
+      // context (to be used in IF), success and failure Rep
+      def getTransition(): Branch[TransitionContext] = {
+        scrut assertIsSubtype head.tpe   // scrut.tpe <:< column.head.tpe confirmed by assertion
+        val av @ ArrayValue(_, xs)  = head.tree
+        val ys                      = if (isRightIgnoring(av)) xs.init else xs
+        val vs                      = ys map (y => newVar(y.stripped.pos, scrut.elemType))
+        def scrutineeCopy           = scrut.id.duplicate
+
+        lazy val tail               = newVar(scrut.pos, scrut.seqType)
+        lazy val lastBinding        = typedValDef(tail, scrutineeCopy DROP ys.size)
+        def elemAt(i: Int)          = typer typed ((scrutineeCopy DOT (scrutineeCopy.tpe member nme.apply))(LIT(i)))
+
+        val bindings =
+          (vs.zipWithIndex map { case (v,i) => typedValDef(v, elemAt(i)) }) ::: List(lastBinding)
+
+        val (nrows, frows) = List.unzip(
+          for ((c, row) <- pats zip rest.row) yield getSubPatterns(ys.size, c) match {
+            case Some(ps) => (Some(row insert ps), if (mustCheck(c, av)) Some(row insert c) else None)
+            case None     => (None, Some(row insert c))
+          })
+
+        val succ = makeSuccRep(vs, tail, nrows flatMap (x => x))
+        val fail = mkFail(frows flatMap (x => x))
+        def transition = (thenp: Tree, elsep: Tree) =>
+          IF (getPrecondition(scrutineeCopy, xs.length)) THEN squeezedBlock(bindings, thenp) ELSE elsep
+
+        Branch(TransitionContext(transition), succ, Some(fail))
+      }
+
+      protected def lengthCheck(tree: Tree, len: Int, op: TreeFunction2) = {
+        def compareOp = head.tpe member nme.lengthCompare  // symbol for "lengthCompare" method
+        typer typed op((tree.duplicate DOT compareOp)(LIT(len)), ZERO)
+      }
+
+      // precondition for matching: sequence is exactly length of arg
+      protected def getPrecondition(tree: Tree, lengthArg: Int) =
+        lengthCheck(tree, lengthArg, _ ANY_== _)
+
+      final def tree() = {
+        val Branch(TransitionContext(transition), succ, Some(fail)) = this.getTransition
+        transition(succ.toTree, fail.toTree)
+      }
+    }
+
+    /** handle sequence pattern and ArrayValue with star patterns
+     */
+    final class MixSequenceStar(pats: Patterns, rest:Rep) extends MixSequence(pats, rest) {
+      // in principle, we could optimize more, but variable binding gets complicated (@todo use finite state methods instead)
+      override def getSubPatterns(minlen: Int, x: Tree) = x match {
+        case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length   == minlen) =>  // Seq(p1,...,pN)
+          Some(xs ::: gen.mkNil :: EmptyTree :: Nil)
+        case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 == minlen) =>  // Seq(p1,...,pN,_*)
+          Some(                                   removeStar(xs) ::: EmptyTree :: Nil)
+        case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1  < minlen) =>  // Seq(p1..,pJ,_*)   J < N
+          Some(                                  getDummies(minlen + 1) ::: x :: Nil)
+        case EmptyTree | Ident(nme.WILDCARD)      =>
+          Some(                                  getDummies(minlen + 1          + 1))
+        case _                                    =>
+          None
+
+      }
+
+      override protected def makeSuccRep(vs: List[Symbol], tail: Symbol, nrows: List[Row]) =
+        mkNewRep(vs ::: List(tail), rest.temp, nrows)
+
+      // precondition for matching - sequence is at least length of (arg - 1)
+      // I believe the "- 1" is to remove the _* term.
+      override protected def getPrecondition(tree: Tree, lengthArg: Int) =
+        lengthCheck(tree, lengthArg - 1, _ ANY_>= _)
     }
 
-    private val NPAD = 15
+    // @todo: equals test for same constant
+    class MixEquals(val pats: Patterns, val rest: Rep) extends RuleApplication {
+      /** condition (to be used in IF), success and failure Rep */
+      final def getTransition(): (Branch[Tree], Symbol) = {
+        val vlue = (head.tpe: @unchecked) match {
+          case TypeRef(_,_,List(SingleType(pre,sym))) => REF(pre, sym)
+          case TypeRef(_,_,List(PseudoType(o)))       => o.duplicate
+        }
+        assert(vlue.tpe ne null, "value tpe is null")
+        val vs        = head.boundVariables
+        val nsuccFst  = rest.row.head.insert2(List(EmptyTree), vs, scrut.sym)
+        val failLabel = owner.newLabel(scrut.pos, newName(scrut.pos, "failCont%")) // warning, untyped
+        val sx        = shortCut(failLabel)     // register shortcut
+        val nsuccRow  = nsuccFst :: Row(getDummies( 1 /* scrutinee */ + rest.temp.length), NoBinding, NoGuard, sx) :: Nil
+
+        // todo: optimize if no guard, and no further tests
+        val nsucc = mkNewRep(Nil, rest.temp, nsuccRow)
+        val nfail = mkFail(List.map2(rest.row.tail, pats.tail.ps)(_ insert _))
+
+        (Branch(typer typed (scrut.id ANY_== vlue), nsucc, Some(nfail)), failLabel)
+      }
 
-    private def typeToString(t: Type): String = t match {
-      case NoType => "x"
-      case x      => x.toString
+      final def tree() = {
+        val (Branch(cond, srep, Some(frep)), failLabel) = this.getTransition
+        val fail  = typer typed frep.toTree
+        failLabel setInfo MethodType(Nil, fail.tpe)
+
+        typer typed(
+          IF (handleOuter(cond)) THEN srep.toTree ELSE LabelDef(failLabel, Nil, fail)
+        )
+      }
     }
-    private def symbolToString(s: Symbol): String = s match {
-      case x  => x.toString
+
+    /** mixture rule for type tests
+    **/
+    class MixTypes(val pats: Patterns, val rest: Rep) extends RuleApplication {
+      private def subpatterns(p: Tree): List[Tree] = p match {
+        case Bind(_, p)                                                 => subpatterns(p)
+        case app @ Apply(fn, ps) if app.tpe.isCaseClass && fn.isType    => if (pats.isCaseHead) ps else pats.dummies
+        case Apply(fn, xs) if !xs.isEmpty || fn.isType                  => abort("strange Apply")
+        case _                                                          => pats.dummies
+      }
+
+      // moreSpecific: more specific patterns
+      //     subsumed: more general patterns (subsuming current), row index and subpatterns
+      //    remaining: remaining, row index and pattern
+      def join[T](xs: List[Option[T]]): List[T] = xs.flatMap(x => x)
+      val (moreSpecific, subsumed, remaining) : (List[Tree], List[(Int, List[Tree])], List[(Int, Tree)]) = unzip3(
+        for ((pat @ Stripped(spat), j) <- pats.zip) yield {
+          def eqHead(tpe: Type)         = pats.headType =:= tpe
+          def alts(yes: Tree, no: Tree) = if (eqHead(pat.tpe)) yes else no
+
+          lazy val isDef                = isDefaultPattern(pat)
+          lazy val cmp: TypeComparison  = spat.tpe cmp pats.headType  // contains type info about pattern's type vs. head pattern
+          lazy val dummy                = (j, pats.dummies)
+          lazy val pass                 = (j, pat)
+          lazy val subs                 = (j, subpatterns(pat))
+
+          import cmp._  // imports xIsaY, etc.
+
+          // each pattern will yield a triple of options corresponding to the three lists,
+          // which will be flattened down to the values
+          implicit def mkOpt[T](x: T): Option[T] = Some(x)    // limits noise from Some(value)
+          (spat match {
+            case LIT(null) if !eqHead(spat.tpe)               => (None, None, pass)           // special case for constant null
+            case _ if pats.isObjectTest(pat)                  => (EmptyTree, dummy, None)     // matching an object
+            case Typed(p @ Stripped(_: UnApply), _) if xIsaY  => (p, dummy, None)             // <:< is never <equals>
+            case q @ Typed(pp, _) if xIsaY                    => (alts(pp, q), dummy, None)   // never =:= for <equals>
+            // this next line inflicted great suffering upon innocents
+            // case z: UnApply                                   => (None, None, pass)
+            // XXX note - while removing the above line fixed the abhorrent "wrong answer" behavior
+            // illustrated in bug #1697, it then led to "consistency problem in target generation"
+            // failures with extractors in the first position (see classifyPat.)
+            case z: UnApply                                   => (EmptyTree, dummy, pass)
+            case _ if erased.xIsaY || xIsaY && !isDef         => (alts(EmptyTree, pat), subs, None) // never =:= for <equals>
+            case _ if erased.yIsaX || yIsaX || isDef          => (EmptyTree, dummy, pass)     // subsuming (matched *and* remaining pattern)
+            case _                                            => (None, None, pass)
+          }) : (Option[Tree], Option[(Int, List[Tree])], Option[(Int, Tree)])
+        }
+      ) match { case (x,y,z) => (join(x), join(y), join(z)) }
+
+      override def toString = {
+        "MixTypes(%s: %s) {\n  moreSpecific: %s\n  subsumed: %s\n  remaining: %s\n}".format(
+          scrut, scrut.tpe, moreSpecific, subsumed, remaining
+        )
+      }
+
+      /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */
+      final def getTransition(): Branch[Scrutinee] = {
+        val casted = scrut casted pats.headType
+
+        // succeeding => transition to translate(subsumed) (taking into account more specific)
+        val nmatrix = {
+          val ms = moreSpecific exists (_ != EmptyTree)
+          val accessorTemps =
+            if (!pats.isCaseHead) Nil
+            else casted.accessors map (meth => newVar(scrut.pos, (casted.tpe memberType meth).resultType, scrut.flags))
+          val subtestTemps = if (!ms) Nil else List(casted.sym)
+          val subtests =
+            if (!ms) subsumed
+            else moreSpecific.zip(subsumed) map { case (mspat, (j, pats)) => (j, mspat::pats) }
+          val ntriples =
+            for ((j, ps) <- subtests ; val Strip(vs, thePat) = pats(j)) yield
+              (rest row j).insert2(ps, vs, casted.sym)
+
+          make(subtestTemps ::: accessorTemps ::: rest.temp, ntriples)
+        }
+
+        // fails      => transition to translate(remaining)
+        val nmatrixFail: Option[Rep] = {
+          val ntriples = for ((j, pat) <- remaining) yield (rest row j) insert pat
+          if (ntriples.isEmpty) None else Some(mkFail(ntriples))
+        }
+
+        Branch(casted, nmatrix, nmatrixFail)
+      }
+
+      final def tree(): Tree = {
+        val Branch(casted, srep, frep) = this.getTransition
+        val cond = condition(casted.tpe, scrut)
+        val succ = srep.toTree
+        val fail = frep map (_.toTree) getOrElse (failTree)
+
+        // dig out case field accessors that were buried in (***)
+        val cfa       = if (!pats.isCaseHead) Nil else casted.accessors
+        val caseTemps = srep.temp match { case x :: xs if x == casted.sym => xs ; case x => x }
+        def needCast  = if (casted.sym ne scrut.sym) List(VAL(casted.sym) === (scrut.id AS_ANY casted.tpe)) else Nil
+        val vdefs     = needCast ::: (
+          for ((tmp, accessor) <- caseTemps zip cfa) yield
+            typedValDef(tmp, typer typed fn(casted.id, accessor))
+        )
+
+        typer typed (IF (cond) THEN squeezedBlock(vdefs, succ) ELSE fail)
+      }
     }
-    private def treeToString(t: Tree): String = t.stripped 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 + ")"
+
+    case class Row(pat: List[Tree], subst: Bindings, guard: Guard, bx: Int) {
+      def insert(h: Tree)                               = copy(pat = h :: pat)
+      def insert(hs: List[Tree])                        = copy(pat = hs ::: pat)    // prepends supplied tree
+      def replace(hs: List[Tree])                       = copy(pat = hs)            // substitutes for patterns
+      def rebind(b: Bindings)                           = copy(subst = b)           // substitutes for bindings
+      def insert2(hs: List[Tree], vs: Iterable[Symbol], temp: Symbol) =             // prepends and prepends
+        copy(pat = hs ::: pat, subst = subst.add(vs, temp))
+
+      def insert(p: Pattern)                            = copy(pat = p.tree :: pat) // transitioning to patterns
+
+      /** returns true if the patterns in this row cover a type symbols "combination" and there is no guard
+       *  @param comb pairs of (column index, type symbol)
+       */
+      def covers(comb: List[Combo]) = {
+        val results = for (Combo(i, sym) <- comb ; val p = pat(i).stripped) yield p match {
+          case _ if isDefaultPattern(p)   => true
+          case _: UnApply | _: ArrayValue => true
+          case _                          => p.tpe coversSym sym
+        }
+
+        guard.isEmpty && (results forall (true ==))
+      }
+
+      // returns this row with alternatives expanded
+      def expand(classifyPat: (Tree, Int) => Tree): List[Row] = {
+        def isAlternative(p: Tree) = cond(p.stripped) { case Alternative(_) => true }
+        def getAlternativeBranches(p: Tree): List[Tree] = {
+          def get_BIND(pctx: TreeFunction1, p:Tree): List[Tree] = p match {
+            case b @ Bind(n,p)   => get_BIND((x: Tree) => pctx(treeCopy.Bind(b, n, x) setType x.tpe), p)
+            case Alternative(ps) => ps map pctx
+          }
+          logAndReturn("get_BIND: ", get_BIND(x => x, p))
+        }
+
+        val indexOfAlternative            = pat findIndexOf isAlternative
+        val pats: List[Tree]              = List.map2(pat, pat.indices.toList)(classifyPat)
+        lazy val (prefix, alts :: suffix) = pats splitAt indexOfAlternative
+        lazy val alternativeBranches      = getAlternativeBranches(alts) map (x => replace(prefix ::: x :: suffix))
+
+        if (indexOfAlternative == -1) List(replace(pats)) else alternativeBranches
+      }
+      override def toString() = {
+        val patStr = pat.mkString
+        val others = List(subst, guard) map (_.toString) filter (_ != "")
+        val otherStr = if (others.isEmpty) "" else " // " + others.mkString(" ")
+
+        "Row(%d) %s%s".format(bx, patStr, otherStr)
+      }
     }
+    case class Combo(index: Int, sym: Symbol) {}
+    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])
+
+    case class Rep(val temp: List[Symbol], val row: List[Row]) {
+      /** converts this to a tree - performs recursive call to translation in the process to get sub reps
+       */
+      final def toTree(): Tree =
+        this.applyRule.tree
+
+      private def toUse(s: Symbol) =
+         (s hasFlag Flags.MUTABLE) &&                 // indicates that have not yet checked exhaustivity
+        !(s hasFlag Flags.TRANS_FLAG) &&              // indicates @unchecked
+         (s.tpe.typeSymbol hasFlag Flags.SEALED)
+
+      // the superclass is taken if it is not abstract
+      private def countSuper(s: Symbol): Set[Symbol]  = if (s hasFlag Flags.ABSTRACT) emptySymbolSet else Set(s)
+      private def countSymbol(s: Symbol): Set[Symbol] = candidates(s) ++ countSuper(s)
+      private def candidates(s: Symbol): Set[Symbol]  =
+        if (s hasFlag Flags.SEALED) s.children flatMap countSymbol
+        else emptySymbolSet
+
+      private def setsToCombine: List[(Int, Set[Symbol])] =
+        for ((sym, i) <- temp.zipWithIndex ; if toUse(sym)) yield {
+          sym resetFlag Flags.MUTABLE
+          (i, candidates(sym.tpe.typeSymbol))
+        }
 
-    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
-    })
-    private def pad(s: String): String = "%%%ds" format (NPAD - 1) format s
-  }
+      // computes cartesian product, keeps indices available
+      private def combine(colcom: List[(Int, Set[Symbol])]): List[List[Combo]] = colcom match {
+        case Nil              => Nil
+        case (i, syms) :: Nil => syms.toList map (s => List(Combo(i, s)))
+        case (i, syms) :: cs  => for (s <- syms.toList; rest <- combine(cs)) yield Combo(i, s) :: rest
+      }
+
+      private def comboCovers(combo: List[Combo]) = row exists (_ covers combo)
 
-  /** creates initial clause matrix
-   */
-  final def initRep(roots: List[Symbol], cases: List[Tree], rep: RepFactory)(implicit theOwner: Symbol) = {
-    val (rows, targets, vss): (List[Option[Row]], List[Tree], List[List[Symbol]]) = unzip3(
-      for ((CaseDef(pat, g, b), bx) <- cases.zipWithIndex) yield {  // stash away pvars and bodies for later
-
-        def mkRow(ps: List[Tree]) = Some(Row(ps, NoBinding, Guard(g), bx))
-        def rowForPat: Option[Row] = pat match {
-          case _ if roots.length <= 1 => mkRow(List(pat))
-          case Apply(fn, pargs)       => mkRow(pargs)
-          case Ident(nme.WILDCARD)    => mkRow(getDummies(roots.length))
-          case _                      => None
+      def init: this.type = {
+        val allcomb = combine(setsToCombine)
+        if (allcomb forall comboCovers) return this
+
+        // if we reach here, patterns were not exhaustive
+        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 " + temp.indices.map(mkPad(open, _)).mkString + "\n"
 
-        (rowForPat, b, definedVars(pat))
+        val missingCombos = (allcomb filter (open => row.forall(!_.covers(open))) map mkMissingStr).mkString
+        cunit.warning(temp.head.pos, "match is not exhaustive!\n" + missingCombos)
+        this
       }
-    )
 
-    // flatMap the list of options yields the list of values
-    rep.make(roots, rows.flatMap(x => x), targets, vss)
-  }
+      /*   internal representation is (temp:List[Symbol], row:List[Row])
+       *
+       *         tmp1       tmp_m
+       */
+      final def applyRule(): RuleApplication = {
+        def dropIndex[T](xs: List[T], n: Int) = (xs take n) ::: (xs drop (n + 1))
+        if (row.isEmpty)
+          return ErrorRule()
+
+        val Row(pats, subst, g, bx) :: xs = row
+        var bnd = subst
+        for (((rpat, t), px) <- pats zip temp zipWithIndex) {
+          val Strip(vs, p) = rpat
+
+          if (isDefaultPattern(p)) bnd = bnd.add(vs, t)
+          else {
+            // Row( _  ... _ p_1i  ...  p_1n   g_m  b_m ) :: rows
+            // cut out column px that contains the non-default pattern
+            val column    = rpat :: (row.tail map (_ pat px))
+            val restTemp  = dropIndex(temp, px)
+            val restRows  = row map (r => r replace dropIndex(r.pat, px))
+            val mr        = MixtureRule(new Scrutinee(t), column, make(restTemp, restRows))
+
+            // TRACE("Mixture rule is = " + mr.getClass)
+            return mr
+          }
+        }
+        // Row(   _   ...   _     g_1  b_1 ) :: rows     it's all default patterns
+        val rest = if (g.isEmpty) null else make(temp, xs)    // TODO - why null?
+        VariableRule(bnd, g, rest, bx)
+      }
 
-  final def newVar(
-    pos: Position,
-    tpe: Type,
-    flags: List[Long] = Nil,
-    name: Name = null
-  )(implicit theOwner: Symbol): Symbol = {
-    val n: Name = if (name == null) newName(pos, "temp") else name
-    // careful: pos has special meaning
-    theOwner.newVariable(pos, n) setInfo tpe setFlag (0L /: flags)(_|_)
-  }
+      // a fancy toString method for debugging
+      override def toString() = {
+        val tempStr = (temp map (t => pad(t.name))).mkString
+        val underlines = tempStr.replaceAll("""\S""", "-")
+        val rowStr = (
+          for (Row(pat, subst, guard, bx) <- row) yield {
+            val extraStr: String = guard.toString + subst
+            "%s %s\n".format(pat map pad mkString, extraStr)
+          }
+        ) mkString
 
-  /** returns the condition in "if (cond) k1 else k2"
-   */
-  final def condition(tpe: Type, scrut: Scrutinee)(implicit typer: Typer, theOwner: Symbol, rep: RepFactory): Tree = {
-    assert(scrut.isDefined)
-    val cond = rep handleOuter (typer typed condition(tpe, scrut.id))
+        if (temp.size == 0) "Rep(%dx%d)".format(temp.size, row.size)
+        else "Rep(%dx%d)\n%s\n%s\n%s".format(temp.size, row.size, tempStr, underlines, rowStr)
+      }
 
-    if (!needsOuterTest(tpe, scrut.tpe, theOwner)) cond
-    else addOuterCondition(cond, tpe, scrut.id, rep.handleOuter)
-  }
+      private val NPAD = 15
 
-  final def condition(tpe: Type, scrutTree: Tree)(implicit typer: Typer): Tree = {
-    assert((tpe ne NoType) && (scrutTree.tpe ne NoType))
-    def equalsRef         = REF(tpe.termSymbol) ANY_== scrutTree
-    def isInst            = scrutTree IS tpe
-    def isAnyRef(t: Type) = t <:< definitions.AnyRefClass.tpe
+      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 = t.stripped 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 + ")"
+      }
+
+      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
+      })
+      private def pad(s: String): String = "%%%ds" format (NPAD - 1) format s
+    }
+
+    /** Executes the match algorithm. */
+    final def execute(roots: List[Symbol], cases: List[Tree]) = {
+      val (rows, targets, vss): (List[Option[Row]], List[Tree], List[List[Symbol]]) = unzip3(
+        for ((CaseDef(pat, g, b), bx) <- cases.zipWithIndex) yield {  // stash away pvars and bodies for later
+
+          def mkRow(ps: List[Tree]) = Some(Row(ps, NoBinding, Guard(g), bx))
+          def rowForPat: Option[Row] = pat match {
+            case _ if roots.length <= 1 => mkRow(List(pat))
+            case Apply(fn, pargs)       => mkRow(pargs)
+            case Ident(nme.WILDCARD)    => mkRow(getDummies(roots.length))
+            case _                      => None
+          }
 
-    tpe match {
-      case ct: ConstantType => ct.value match {                  // constant
-          case v @ Constant(null) if isAnyRef(scrutTree.tpe)  => scrutTree ANY_EQ NULL
-          case v                                              => scrutTree ANY_== Literal(v)
+          (rowForPat, b, definedVars(pat))
         }
-      case _: SingletonType =>
-        if (tpe.termSymbol.isModule) equalsRef  // object
-        else typer typed { if (tpe.prefix ne NoPrefix) isInst else equalsRef }
-      case _ =>
-        if (scrutTree.tpe <:< tpe && isAnyRef(tpe)) typer typed (scrutTree OBJ_!= NULL)
-        else isInst
+      )
+
+      // flatMap the list of options yields the list of values
+      make(roots, rows.flatMap(x => x), targets, vss)
     }
-  }
 
-  /** adds a test comparing the dynamic outer to the static outer */
-  final def addOuterCondition(cond: Tree, tpe2test: Type, scrut: Tree, handleOuter: Tree=>Tree) = {
-    val theRef = handleOuter(tpe2test match {
-      case TypeRef(NoPrefix, _, _)          => abort("assertion failed: NoPrefix")
-      case TypeRef(ThisType(clazz), _, _)   => THIS(clazz)
-      case TypeRef(prefix, _, _)            => REF(prefix.prefix, prefix.termSymbol)
-    })
-
-    outerAccessor(tpe2test.typeSymbol) match {
-      case NoSymbol => ifDebug(cunit.warning(scrut.pos, "no outer acc for "+tpe2test.typeSymbol)) ; cond
-      case outerAcc => cond AND (((scrut AS_ANY tpe2test) DOT outerAcc)() ANY_EQ theRef)
+    /** returns the condition in "if (cond) k1 else k2"
+     */
+    final def condition(tpe: Type, scrut: Scrutinee): Tree = {
+      assert(scrut.isDefined)
+      val cond = handleOuter(condition(tpe, scrut.id))
+
+      if (!needsOuterTest(tpe, scrut.tpe, owner)) cond
+      else addOuterCondition(cond, tpe, scrut.id, handleOuter)
+    }
+
+    final def condition(tpe: Type, scrutTree: Tree): Tree = {
+      assert((tpe ne NoType) && (scrutTree.tpe ne NoType))
+
+      def isAnyRef(t: Type) = t <:< definitions.AnyRefClass.tpe
+      def useEqTest         = tpe.termSymbol.isModule || (tpe.prefix eq NoPrefix)
+
+      typer typed (tpe match {
+        case ct: ConstantType => ct.value match {
+            case v @ Constant(null) if isAnyRef(scrutTree.tpe)  => scrutTree ANY_EQ NULL
+            case v                                              => scrutTree ANY_== Literal(v)
+          }
+        case _: SingletonType if useEqTest                      => REF(tpe.termSymbol) ANY_== scrutTree
+        case _ if scrutTree.tpe <:< tpe && isAnyRef(tpe)        => scrutTree OBJ_!= NULL
+        case _                                                  => scrutTree IS tpe
+      })
+    }
+
+    /** adds a test comparing the dynamic outer to the static outer */
+    final def addOuterCondition(cond: Tree, tpe2test: Type, scrut: Tree, handleOuter: Tree=>Tree) = {
+      val theRef = handleOuter(tpe2test match {
+        case TypeRef(NoPrefix, _, _)          => abort("assertion failed: NoPrefix")
+        case TypeRef(ThisType(clazz), _, _)   => THIS(clazz)
+        case TypeRef(prefix, _, _)            => REF(prefix.prefix, prefix.termSymbol)
+      })
+
+      outerAccessor(tpe2test.typeSymbol) match {
+        case NoSymbol => ifDebug(cunit.warning(scrut.pos, "no outer acc for "+tpe2test.typeSymbol)) ; cond
+        case outerAcc => cond AND (((scrut AS_ANY tpe2test) DOT outerAcc)() ANY_EQ theRef)
+      }
     }
   }
 }
diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala
index be92626aef..4eabab920a 100644
--- a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala
+++ b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala
@@ -105,8 +105,6 @@ trait PatternNodes extends ast.TreeDSL
     }
   }
 
-  final def DBG(x: => String)   = if (settings.debug.value) Console.println(x)
-
   final def getDummies(i: Int): List[Tree] = List.fill(i)(EmptyTree)
 
   def makeBind(vs: List[Symbol], pat: Tree): Tree = vs match {
diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
index 3fe0f908a9..c4c5cbf047 100644
--- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
+++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala
@@ -5,6 +5,26 @@
  */
 // $Id$
 
+/**
+ * Simple pattern types:
+ *
+ * 1 Variable               x
+ * 3 Literal                56
+ *
+ * Types which must be decomposed into conditionals and simple types:
+ *
+ * 2 Typed                  x: Int
+ * 4 Stable Identifier      Bob
+ * 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    --
+ */
+
 package scala.tools.nsc.matching
 
 import util.Position
@@ -18,7 +38,7 @@ import scala.util.NameTransformer.decode
  *  @author Burak Emir
  */
 trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
-  self: transform.ExplicitOuter with PatternNodes with ParallelMatching with CodeFactory =>
+  self: transform.ExplicitOuter with PatternNodes with ParallelMatching =>
 
   import global.{ typer => _, _ }
   import analyzer.Typer;
@@ -33,9 +53,95 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
 
   final val settings_squeeze = settings.Xsqueeze.value == "on"
 
-  // check special case Seq(p1,...,pk,_*)
-  protected def isRightIgnoring(p: ArrayValue): Boolean =
-    !p.elems.isEmpty && cond(unbind(p.elems.last)) { case Star(q) => isDefaultPattern(q) }
+  /** Contains data structures which the match algorithm implementation
+   *  requires but which aren't essential to the algorithm itself.
+   */
+  case class MatchMatrixContext(
+    handleOuter: TreeFunction1,
+    typer: Typer,
+    owner: Symbol)
+  {
+    def newVar(
+      pos: Position,
+      tpe: Type,
+      flags: List[Long] = Nil,
+      name: Name = null): Symbol =
+    {
+      val n: Name = if (name == null) newName(pos, "temp") else name
+      // careful: pos has special meaning
+      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)
+      }
+      typer typed (VAL(x) === finalRhs)
+    }
+
+    def squeezedBlock(vds: List[Tree], exp: Tree): Tree =
+      if (settings_squeeze) Block(Nil, squeezedBlock1(vds, exp))
+      else                  Block(vds, exp)
+
+    private def squeezedBlock1(vds: List[Tree], exp: Tree): Tree = {
+      class RefTraverser(sym: Symbol) extends Traverser {
+        var nref, nsafeRef = 0
+        override def traverse(tree: Tree) = tree match {
+          case t: Ident if t.symbol eq sym =>
+            nref += 1
+            if (sym.owner == currentOwner) // oldOwner should match currentOwner
+              nsafeRef += 1
+
+          case LabelDef(_, args, rhs) =>
+            (args dropWhile(_.symbol ne sym)) match {
+              case Nil  =>
+              case _    => nref += 2  // cannot substitute this one
+            }
+            traverse(rhs)
+          case t if nref > 1 =>       // abort, no story to tell
+          case t =>
+            super.traverse(t)
+        }
+      }
+
+      class Subst(sym: Symbol, rhs: Tree) extends Transformer {
+        var stop = false
+        override def transform(tree: Tree) = tree match {
+          case t: Ident if t.symbol == sym =>
+            stop = true
+            rhs
+          case _ => if (stop) tree else super.transform(tree)
+        }
+      }
+
+      lazy val squeezedTail = squeezedBlock(vds.tail, exp)
+      def default = squeezedTail match {
+        case Block(vds2, exp2) => Block(vds.head :: vds2, exp2)
+        case exp2              => Block(vds.head :: Nil,  exp2)
+      }
+
+      if (vds.isEmpty) exp
+      else vds.head match {
+        case vd: ValDef =>
+          val sym = vd.symbol
+          val rt = new RefTraverser(sym)
+          rt.atOwner (owner) (rt traverse squeezedTail)
+
+          rt.nref match {
+            case 0                      => squeezedTail
+            case 1 if rt.nsafeRef == 1  => new Subst(sym, vd.rhs) transform squeezedTail
+            case _                      => default
+          }
+        case _          =>
+          default
+      }
+    }
+  }
 
   /** handles all translation of pattern matching
    */
@@ -44,12 +150,13 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
     cases: List[CaseDef],
     doCheckExhaustive: Boolean,
     owner: Symbol,
-    handleOuter: Tree => Tree)
-    (implicit typer: Typer): Tree =
+    handleOuter: TreeFunction1,
+    localTyper: Typer): Tree =
   {
-    implicit val theOwner = owner
-    implicit val rep = new RepFactory(handleOuter, typer)
-    val flags = if (doCheckExhaustive) Nil else List(Flags.TRANS_FLAG)
+    val flags     = if (doCheckExhaustive) Nil else List(Flags.TRANS_FLAG)
+    val context   = MatchMatrixContext(handleOuter, localTyper, owner)
+
+    import context._
 
     def matchError(obj: Tree)   = atPos(selector.pos)(THROW(MatchErrorClass, obj))
     def caseIsOk(c: CaseDef)    = cond(c.pat) { case _: Apply | Ident(nme.WILDCARD) => true }
@@ -80,9 +187,9 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
         (List(root), List(vdef), failTree)
     }
 
-    implicit val fail: Tree = theFailTree
-    val irep = initRep(tmps, cases, rep)
-    val mch = typer typed irep.toTree
+    val matrix  = new MatchMatrix(context, theFailTree)
+    val rep     = matrix.execute(tmps, cases)
+    val mch     = typer typed rep.toTree
     var dfatree = typer typed Block(vds, mch)
 
     // TRACE("handlePattern(\n  tmps = %s\n  cases = %s\n  rep = %s\n  initRep = %s\n)",
@@ -91,9 +198,9 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter {
 
     // cannot use squeezedBlock because of side-effects, see t275
     for ((cs, bx) <- cases.zipWithIndex)
-      if (!rep.isReached(bx)) cunit.error(cs.body.pos, "unreachable code")
+      if (!matrix.isReached(bx)) cunit.error(cs.body.pos, "unreachable code")
 
-    dfatree = rep cleanup dfatree
+    dfatree = matrix cleanup dfatree
     resetTraverser traverse dfatree
     // TRACE("dfatree(2) = " + toCompactString(dfatree))
     dfatree
diff --git a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala
index a27f6989e1..bd5e71d23c 100644
--- a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala
+++ b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala
@@ -8,8 +8,8 @@ package scala.tools.nsc.transform
 
 import symtab._
 import Flags.{ CASE => _, _ }
-import scala.collection.mutable.{HashMap, ListBuffer}
-import matching.{TransMatcher, PatternNodes, CodeFactory, ParallelMatching}
+import scala.collection.mutable.ListBuffer
+import matching.{ TransMatcher, PatternNodes, ParallelMatching }
 
 /** This class ...
  *
@@ -19,7 +19,6 @@ import matching.{TransMatcher, PatternNodes, CodeFactory, ParallelMatching}
 abstract class ExplicitOuter extends InfoTransform
       with TransMatcher
       with PatternNodes
-      with CodeFactory
       with ParallelMatching
       with TypingTransformers
       with ast.TreeDSL
@@ -460,7 +459,7 @@ abstract class ExplicitOuter extends InfoTransform
           ExplicitOuter.this.resultType = tree.tpe
 
           val t = atPos(tree.pos) {
-            val t_untyped = handlePattern(nselector, ncases, checkExhaustive, currentOwner, transform)(localTyper)
+            val t_untyped = handlePattern(nselector, ncases, checkExhaustive, currentOwner, transform, localTyper)
             /* if @switch annotation is present, verify the resulting tree is a Match */
             if (requireSwitch) t_untyped match {
               case Block(_, Match(_, _))  => // ok