[vpm] emitting switches -- BodyTreeMaker

1) introduce BodyTreeMaker to get rid of special casing for body
   now each case is a list of TreeMakers rather than a pair of such a list and a tree
   needed to do this since emitting switches requires access to the untranslated body

2) emitting switches
    - alternatives are flattened: each alternative block ends with a jump to the next alternative (if there is one)
    - to avoid stack overflow in typedMatch: detect when translateMatch returns a Match

the patch to uncurry would be nicer with an extractor, but that breaks due to a bug in old patmat

made trees into dags again -- NPE in erasure

tree.duplicate seems to break lambdalift because it
does not give fresh symbols (or trees?) to the valdefs
for the arguments of duplicated functions

duplicate enclosing tree, not subtrees

improved propagateSubstitution for AlternativesTreeMaker

 - it now propagates to all its alternatives, so we don't have to do that in chainBefore
 - by making propagation more regular, a bug in substitution in AlternativesTreeMaker manifested itself
   it introduced a new binder, unnecessarily, which then was unbound -- now reusing binder of outer pattern

having removeSubstOnly in propagateSubstitution unveiled a bug: guard treemaker should substitute

move fixerUpper closer to what it fixes up

9 files changed, 319 insertions, 166 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
index e26a0d59e8..3f0a0fac1a 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
@@ -1078,6 +1078,7 @@ abstract class GenICode extends SubComponent  {
             }
 
             caseCtx = genLoad(body, tmpCtx, generatedType)
+            // close the block unless it's already been closed by the body, which closes the block if it ends in a jump (which is emitted to have alternatives share their body)
             caseCtx.bb.closeWith(JUMP(afterCtx.bb) setPos caze.pos)
           }
           ctx1.bb.emitOnly(
diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala
index 6ac28f2fe3..90f46206c5 100644
--- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala
+++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala
@@ -290,38 +290,70 @@ abstract class UnCurry extends InfoTransform
           val idparam = m.paramss.head.head
           val substParam = new TreeSymSubstituter(List(vparam), List(idparam))
           def substTree[T <: Tree](t: T): T = substParam(resetLocalAttrs(t))
-          object VirtPatmatOpt {
-            object Last {
-              def unapply[T](xs: List[T]) = xs.lastOption
-            }
-            // keep this in synch by what's generated by combineCases/runOrElse
-            object MatcherBlock {
-              def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree])] = matcher match { // TODO: BUG the unapplySeq version of the case below does not seem to work in virtpatmat??
-                case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) => Some(zero, x, matchRes, keepGoing, stats)
-                case _ => None
+
+          // waiting here until we can mix case classes and extractors reliably (i.e., when virtpatmat becomes the default)
+          // object VirtPatmatOpt {
+          //   object Last {
+          //     def unapply[T](xs: List[T]) = xs.lastOption
+          //   }
+          //   // keep this in synch by what's generated by combineCases/runOrElse
+          //   object MatcherBlock {
+          //     def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree])] = matcher match { // TODO: BUG the unapplySeq version of the case below does not seem to work in virtpatmat??
+          //       case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) => Some(zero, x, matchRes, keepGoing, stats)
+          //       case _ => None
+          //     }
+          //   }
+          //   // TODO: virtpatmat use case: would be nice if could abstract over the repeated pattern more easily
+          //   // case Block(Last(P)) =>
+          //   // case P =>
+          //   def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree], Tree => Tree)] = matcher match {
+          //     case MatcherBlock(zero, x, matchRes, keepGoing, stats) => Some(zero, x, matchRes, keepGoing, stats, identity[Tree])
+          //     case Block(outerStats, MatcherBlock(zero, x, matchRes, keepGoing, stats)) => Some(zero, x, matchRes, keepGoing, stats, inner => Block(outerStats, inner))
+          //     case b => treeBrowser browse b; None
+          //   }
+          // }
+
+          // TODO: optimize duplication, but make sure ValDef's introduced by wrap are treated correctly
+          def dupMatch(selector: Tree, cases: List[CaseDef], wrap: Match => Tree = identity) = {
+            def transformCase(cdef: CaseDef): CaseDef =
+              CaseDef(cdef.pat, cdef.guard, Literal(Constant(true)))
+            def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false)))
+
+            gen.mkUncheckedMatch(
+              if (cases exists treeInfo.isDefaultCase) Literal(Constant(true))
+              else substTree(wrap(Match(selector, (cases map transformCase) :+ defaultCase)).duplicate)
+            )
+          }
+
+          def dupVirtMatch(zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], wrap: Block => Tree = identity) = {
+            object dropMatchResAssign extends Transformer {
+              // override val treeCopy = newStrictTreeCopier // will duplicate below
+              override def transform(tree: Tree): Tree = tree match {
+                // don't compute the result of the match -- remove the block for the RHS (emitted by pmgen.one), except for the assignment to keepGoing
+                case Block(List(matchRes, ass@Assign(keepGoingLhs, falseLit)), zero) if keepGoingLhs.symbol eq keepGoing.symbol =>
+                  Block(List(ass), zero)
+                case _ =>
+                  super.transform(tree)
               }
             }
-            // TODO: virtpatmat use case: would be nice if could abstract over the repeated pattern more easily
-            // case Block(Last(P)) =>
-            // case P =>
-            def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree], Tree => Tree)] = matcher match {
-              case MatcherBlock(zero, x, matchRes, keepGoing, stats) => Some(zero, x, matchRes, keepGoing, stats, identity[Tree])
-              case Block(outerStats, MatcherBlock(zero, x, matchRes, keepGoing, stats)) => Some(zero, x, matchRes, keepGoing, stats, inner => Block(outerStats, inner))
-              case b => treeBrowser browse b; None
-            }
+            val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList
+            val idaBlock = wrap(Block(
+              zero ::
+              x ::
+              /* drop matchRes def */
+              keepGoing ::
+              statsNoMatchRes,
+              NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` by `!keepGoing`
+            ))
+            substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed            
           }
+
           DefDef(m, (fun.body: @unchecked) match {
             case Match(selector, cases) =>
-              def transformCase(cdef: CaseDef): CaseDef =
-                substTree(CaseDef(cdef.pat.duplicate, cdef.guard.duplicate, Literal(Constant(true))))
-              def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false)))
-
-              gen.mkUncheckedMatch(
-                if (cases exists treeInfo.isDefaultCase) Literal(Constant(true))
-                else Match(substTree(selector.duplicate), (cases map transformCase) :+ defaultCase)
-              )
-            // TODO: find a better way to keep this in synch with the code generard by patmatvirtualizer
-            // TODO: check tgt.tpe.typeSymbol isNonBottomSubclass MatchingStrategyClass
+              dupMatch(selector, cases)
+            case Block((vd: ValDef) :: Nil, Match(selector, cases)) => // can't factor this out using an extractor due to bugs in the old pattern matcher
+              dupMatch(selector, cases, m => Block(List(vd), m))
+            // virtpatmat -- TODO: find a better way to keep this in synch with the code generated by patmatvirtualizer
             case Apply(Apply(TypeApply(Select(tgt, nme.runOrElse), targs), args_scrut), args_pm) if opt.virtPatmat =>
               object noOne extends Transformer {
                 override val treeCopy = newStrictTreeCopier // must duplicate everything
@@ -336,28 +368,13 @@ abstract class UnCurry extends InfoTransform
                 }
               }
               substTree(Apply(Apply(TypeApply(Select(tgt.duplicate, tgt.tpe.member("isSuccess".toTermName)), targs map (_.duplicate)), args_scrut map (_.duplicate)), args_pm map (noOne.transform)))
-            // for no-option version of virtpatmat
-            case VirtPatmatOpt(zero, x, matchRes, keepGoing, stats, addOuter) if opt.virtPatmat => import CODE._
-              object dropMatchResAssign extends Transformer {
-                // override val treeCopy = newStrictTreeCopier // will duplicate below
-                override def transform(tree: Tree): Tree = tree match {
-                  // don't compute the result of the match -- remove the block for the RHS (emitted by pmgen.one), except for the assignment to keepGoing
-                  case Block(List(matchRes, ass@Assign(keepGoingLhs, falseLit)), zero) if keepGoingLhs.symbol eq keepGoing.symbol =>
-                    Block(List(ass), zero)
-                  case _ =>
-                    super.transform(tree)
-                }
-              }
-              val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList
-              val idaBlock = addOuter(Block(
-                zero ::
-                x ::
-                /* drop matchRes def */
-                keepGoing ::
-                statsNoMatchRes,
-                NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` by `!keepGoing`
-              ))
-              substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed
+            // for the optimized version of virtpatmat
+            case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) if opt.virtPatmat =>
+              dupVirtMatch(zero, x, matchRes, keepGoing, stats)
+            case Block(outerStats, Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _)) if opt.virtPatmat =>  // can't factor this out using an extractor due to bugs in the old pattern matcher
+              dupVirtMatch(zero, x, matchRes, keepGoing, stats, m => Block(outerStats, m))
+            // case other =>
+            //   treeBrowser browse other
           })
         }
 
@@ -542,6 +559,7 @@ abstract class UnCurry extends InfoTransform
           }
         case ValDef(_, _, _, rhs) =>
           val sym = tree.symbol
+          if (sym eq NoSymbol) throw new IllegalStateException("Encountered Valdef without symbol: "+ tree + " in "+ unit)
           // a local variable that is mutable and free somewhere later should be lifted
           // as lambda lifting (coming later) will wrap 'rhs' in an Ref object.
           if (!sym.owner.isSourceMethod)
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index 17f2d4f96c..ff59cb15f1 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -90,7 +90,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       val scrutSym  = freshSym(scrut.pos, scrutType)
       val okPt = repeatedToSeq(pt)
       // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala  with -Xexperimental
-      fixerUpper(context.owner, scrut.pos)(combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt))
+      combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, context.owner)
     }
 
 
@@ -123,7 +123,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       *
       */
     def translateCase(scrutSym: Symbol, pt: Type)(caseDef: CaseDef) = caseDef match { case CaseDef(pattern, guard, body) =>
-      (translatePattern(scrutSym, pattern) ++ translateGuard(guard), translateBody(body, pt))
+      translatePattern(scrutSym, pattern) ++ translateGuard(guard) :+ translateBody(body, pt)
     }
 
     def translatePattern(patBinder: Symbol, patTree: Tree): List[TreeMaker] = {
@@ -274,11 +274,13 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
     // so that we can return Option's from a match without ambiguity whether this indicates failure in the monad, or just some result in the monad
     // 2) body.tpe is the type of the body after applying the substitution that represents the solution of GADT type inference
     // need the explicit cast in case our substitutions in the body change the type to something that doesn't take GADT typing into account
-    def translateBody(body: Tree, matchPt: Type): Tree = atPos(body.pos)(pmgen.one(body, body.tpe, matchPt))
+    def translateBody(body: Tree, matchPt: Type): TreeMaker =
+      BodyTreeMaker(body, matchPt)
 
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // helper methods: they analyze types and trees in isolation, but they are not (directly) concerned with the structure of the overall translation
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
     object ExtractorCall {
       def apply(unfun: Tree, args: List[Tree]): ExtractorCall = new ExtractorCallRegular(unfun, args)
@@ -643,7 +645,7 @@ defined class Foo */
   }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// the making of the trees
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
   trait TreeMakers {
@@ -657,13 +659,12 @@ defined class Foo */
 
       protected def localSubstitution: Substitution
 
-      private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): TreeMaker = {
+      private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
         if (currSub ne null) {
           println("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst))
           Thread.dumpStack()
         }
         else currSub = outerSubst >> substitution
-        this
       }
       private[this] var currSub: Substitution = null
 
@@ -672,6 +673,17 @@ defined class Foo */
       def treesToHoist: List[Tree] = Nil
     }
 
+    case class TrivialTreeMaker(tree: Tree) extends TreeMaker {
+      val localSubstitution: Substitution = EmptySubstitution
+      def chainBefore(next: Tree, pt: Type): Tree = tree
+    }
+
+    case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker {
+      val localSubstitution: Substitution = EmptySubstitution
+      def chainBefore(next: Tree, pt: Type): Tree = // assert(next eq EmptyTree)
+        atPos(body.pos)(substitution(pmgen.one(body, body.tpe, matchPt))) // since SubstOnly treemakers are dropped, need to do it here
+    }
+
     case class SubstOnlyTreeMaker(localSubstitution: Substitution) extends TreeMaker {
       def chainBefore(next: Tree, pt: Type): Tree = substitution(next)
     }
@@ -680,7 +692,7 @@ defined class Foo */
       val nextBinder: Symbol
 
       // for CSE (used iff optimizingCodeGen)
-      // TODO: factor this out into a separate TreeMaker that gets created when reuse is detected -- don't mutate treemakers
+      // TODO: factor this out -- don't mutate treemakers
       var reused: Boolean = false
       def reusedBinders: List[Symbol] = Nil
       override def treesToHoist: List[Tree] = { import CODE._
@@ -696,7 +708,7 @@ defined class Foo */
       lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
     }
 
-    // TODO: in the process of shifting optimized code gen into the treemakers: complete and make it conditional in the same way as is happening in pmgen
+    // TODO: factor out optimization-specific stuff into codegen
     abstract class CondTreeMaker extends FreshFunTreeMaker { import CODE._
       val cond: Tree
       val res: Tree
@@ -796,39 +808,48 @@ defined class Foo */
       override def toString = "ET"+(prevBinder, patTree)
     }
 
-    case class AlternativesTreeMaker(prevBinder: Symbol, altss: List[List[TreeMaker]], pos: Position) extends FreshFunTreeMaker {
-      val nextBinderTp: Type = prevBinder.info.widen
-      private def inlineNext(next: Tree) = {
-        var okToInline = true
-        var sizeBudget = 20  // yep, totally arbitrary!
-        object travOkToInline extends Traverser { override def traverse(tree: Tree): Unit = if (sizeBudget >= 0) { sizeBudget -= 1; tree match {
-          case TypeApply(_, _) | Apply(_, _) | Select(_, _)
-             | Block(_, _) | Assign(_, _) | If(_, _, _) | Typed(_, _) => super.traverse(tree) // these are allowed if their subtrees are
-          case EmptyTree | This(_) | New(_) | Literal(_) | Ident(_)   => // these are always ok
-          case _ if tree.isType                                       => // these are always ok
-          case _                                                      => okToInline = false //; println("not inlining: "+ (tree, tree.getClass))
-        }}}
-        travOkToInline.traverse(next)
-        // println("(okToInline, sizeBudget): "+ (okToInline, sizeBudget))
-        okToInline && sizeBudget > 0 // must be strict comparison
+    case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker {
+      // don't substitute prevBinder to nextBinder, a set of alternatives does not need to introduce a new binder, simply reuse the previous one
+      val localSubstitution: Substitution = EmptySubstitution
+
+      override private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
+        super.incorporateOuterSubstitution(outerSubst)
+        altss = altss map (alts => propagateSubstitution(alts, substitution))
       }
+
       def chainBefore(next: Tree, pt: Type): Tree = { import CODE._
+        // next does not contain deftrees, is pretty short
+        val canDuplicate = {
+          var okToInline = true
+          var sizeBudget = 100 / (altss.length max 1)  // yep, totally arbitrary!
+          object travOkToInline extends Traverser { override def traverse(tree: Tree): Unit = if (sizeBudget >= 0) { sizeBudget -= 1; tree match {
+            case TypeApply(_, _) | Apply(_, _) | Select(_, _)
+               | Block(_, _) | Assign(_, _) | If(_, _, _) | Typed(_, _) => super.traverse(tree) // these are allowed if their subtrees are
+            case EmptyTree | This(_) | New(_) | Literal(_) | Ident(_)   => // these are always ok
+            case _ if tree.isType                                       => // these are always ok
+            case _                                                      => okToInline = false //; println("not inlining: "+ (tree, tree.getClass))
+          }}}
+          travOkToInline.traverse(next)
+          // println("(okToInline, sizeBudget): "+ (okToInline, sizeBudget))
+          okToInline && sizeBudget > 0 // must be strict comparison
+        }
+
         atPos(pos)(
-          if (inlineNext(next)) {
-            altss map (altTreeMakers =>
-              combineExtractors(propagateSubstitution(altTreeMakers), next.duplicate, pt) // don't substitute prevBinder to nextBinder, beta-reduce application to prevBinder
-            ) reduceLeft pmgen.typedOrElse(pt)
+          if (canDuplicate) {
+            altss map {altTreeMakers =>
+              combineExtractors(altTreeMakers :+ TrivialTreeMaker(substitution(next).duplicate), pt)
+            } reduceLeft pmgen.typedOrElse(pt)
           } else {
-            val rest = freshSym(pos, functionType(List(nextBinderTp), inMatchMonad(pt)), "rest")
+            val rest = freshSym(pos, functionType(List(), inMatchMonad(pt)), "rest")
             // rest.info.member(nme.apply).withAnnotation(AnnotationInfo(ScalaInlineClass.tpe, Nil, Nil))
 
             // one alternative may still generate multiple trees (e.g., an extractor call + equality test)
             // (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers
             val combinedAlts = altss map (altTreeMakers =>
-              combineExtractors(propagateSubstitution(altTreeMakers), REF(rest) APPLY (REF(prevBinder)), pt)
+              combineExtractors(altTreeMakers :+ TrivialTreeMaker(REF(rest) APPLY ()), pt)
             )
             BLOCK(
-              VAL(rest) === pmgen.fun(nextBinder, substitution(next)),
+              VAL(rest) === Function(Nil, substitution(next)),
               combinedAlts reduceLeft pmgen.typedOrElse(pt)
             )
           }
@@ -838,7 +859,7 @@ defined class Foo */
 
     case class GuardTreeMaker(guardTree: Tree) extends TreeMaker {
       val localSubstitution: Substitution = EmptySubstitution
-      def chainBefore(next: Tree, pt: Type): Tree = pmgen.flatMapGuard(guardTree, next)
+      def chainBefore(next: Tree, pt: Type): Tree = pmgen.flatMapGuard(substitution(guardTree), next)
       override def toString = "G("+ guardTree +")"
     }
 
@@ -947,7 +968,7 @@ defined class Foo */
      *
      * intended to be generalised to exhaustivity/reachability checking
      */
-    def doCSE(prevBinder: Symbol, cases: List[(List[TreeMaker], Tree)], pt: Type): List[(List[TreeMaker], Tree)] = {
+    def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
       // a variable in this set should never be replaced by a tree that "does not consist of a selection on a variable in this set" (intuitively)
       val pointsToBound            = collection.mutable.HashSet(prevBinder)
 
@@ -1013,10 +1034,11 @@ defined class Foo */
              | ProductExtractorTreeMaker(_, Some(_), _)             => Havoc
           case AlternativesTreeMaker(_, _, _)                       => Havoc // TODO: can do better here
           case SubstOnlyTreeMaker(_)                                => Top
+          case BodyTreeMaker(_, _)                                  => Havoc
         }, tm)
       }
 
-      val testss = cases.map {case (treeMakers, _) => treeMakers map approximateTreeMaker }
+      val testss = cases.map { _ map approximateTreeMaker }
 
       // interpret:
       val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]]
@@ -1047,7 +1069,7 @@ defined class Foo */
       // then, collapse these contiguous sequences of reusing tests
       // store the result of the final test and the intermediate results in hoisted mutable variables (TODO: optimize: don't store intermediate results that aren't used)
       // replace each reference to a variable originally bound by a collapsed test by a reference to the hoisted variable
-      (testss, cases).zipped map { case (tests, (_, caseBody)) =>
+      testss map { tests =>
         var currDeps = Set[Cond]()
         val (sharedPrefix, suffix) = tests span { test =>
           (test.cond eq Top) || (for(
@@ -1067,63 +1089,186 @@ defined class Foo */
             yield ReusingCondTreeMaker(sharedPrefix map (t => (t.treeMaker, t.reuses map (_.treeMaker)))) :: suffix.map(_.treeMaker)
         } else None
 
-        (collapsedTreeMakers getOrElse tests.map(_.treeMaker), // sharedPrefix need not be empty (but it only contains Top-tests, which are dropped above)
-         caseBody)
+        collapsedTreeMakers getOrElse tests.map(_.treeMaker) // sharedPrefix need not be empty (but it only contains Top-tests, which are dropped above)
       }
     }
 
+    // TODO: non-trivial dead-code elimination
+    // e.g., the following match should compile to a simple instanceof:
+    //   case class Ident(name: String)
+    //   for (Ident(name) <- ts) println(name)
+    def doDCE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
+      // do minimal DCE
+      cases
+    }
 
-    // a foldLeft to accumulate the localSubstitution left-to-right, mutating the treemakers in-place for performance
-    def propagateSubstitution(treeMakers: List[TreeMaker]): List[TreeMaker] = {
-      var accumSubst: Substitution = EmptySubstitution
+
+    def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker])
+
+    // a foldLeft to accumulate the localSubstitution left-to-right
+    // it drops SubstOnly tree makers, since their only goal in life is to propagate substitutions to the next tree maker, which is fullfilled by propagateSubstitution
+    def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = {
+      var accumSubst: Substitution = initial
       treeMakers foreach { maker =>
         maker incorporateOuterSubstitution accumSubst
         accumSubst = maker.substitution
       }
-      treeMakers
+      removeSubstOnly(treeMakers)
     }
 
-    // calls propagateSubstitution on the treemakers
-    def analyzeCases(prevBinder: Symbol, cases: List[(List[TreeMaker], Tree)], pt: Type): List[(List[TreeMaker], Tree)] = {
-      cases foreach { case (pats, _) => propagateSubstitution(pats) }
-      if (optimizingCodeGen) {
-        doCSE(prevBinder, cases, pt)
-      } else cases
-    }
+    object SwitchablePattern { def unapply(pat: Tree) = pat match {
+      case Literal(Constant((_: Byte ) | (_: Short) | (_: Int  ) | (_: Char ))) => true // TODO: Java 7 allows strings in switches
+      case _                                                                    => false
+    }}
+
+    // def isSwitchable(cases: List[(List[TreeMaker], Tree)]): Boolean = {
+    //   def isSwitchableTreeMaker(tm: TreeMaker) = tm match {
+    //     case tm@EqualityTestTreeMaker(_, SwitchablePattern(), _) => true
+    //     case SubstOnlyTreeMaker(_)                               => true
+    //     case AlternativesTreeMaker(_, altss, _)                  => altss forall (_.forall(isSwitchableTreeMaker))
+    //     case _                                                   => false
+    //   }
+    // }
+
+    def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = if (optimizingCodeGen) {
+      def unfold(tms: List[TreeMaker], currLabel: Option[Symbol] = None, nextLabel: Option[Symbol] = None): List[CaseDef] = tms match {
+        // constant
+        case (EqualityTestTreeMaker(_, const@SwitchablePattern(), _)) :: (btm@BodyTreeMaker(body, _)) :: Nil => import CODE._
+          @inline
+          def substedBody  = btm.substitution(body)
+          val labelledBody = currLabel match {
+            case None          => substedBody // currLabel.isEmpty implies nextLabel.isEmpty
+            case Some(myLabel) =>
+              LabelDef(myLabel, Nil,
+                nextLabel match {
+                  case None       => substedBody
+                  case Some(next) => ID(next) APPLY ()
+                }
+              )
+          }
+          List(CaseDef(const, EmptyTree, labelledBody))
+
+        // alternatives
+        case AlternativesTreeMaker(_, altss, _) :: bodyTm :: Nil => // assert(currLabel.isEmpty && nextLabel.isEmpty)
+          val labels  = altss map { alts =>
+            Some(freshSym(NoPosition, MethodType(Nil, pt), "$alt$") setFlag (METHOD | LABEL))
+          }
 
-    def combineCases(scrut: Tree, scrutSym: Symbol, cases0: List[(List[TreeMaker], Tree)], pt: Type): Tree = {
-      var toHoist = List[Tree]()
-      val matcher =
-        if (cases0 nonEmpty) {
-          // when specified, need to propagate pt explicitly (type inferencer can't handle it)
-          val optPt =
-            if (isFullyDefined(pt)) inMatchMonad(pt)
-            else NoType
-
-          val cases = analyzeCases(scrutSym, cases0, pt)
-
-          // map + foldLeft
-          var combinedCases = combineExtractors(cases.head._1, cases.head._2, pt)
-          cases.tail foreach { case (pats, body) =>
-            combinedCases = pmgen.typedOrElse(optPt)(combinedCases, combineExtractors(pats, body, pt))
+          val caseDefs = (altss, labels, labels.tail :+ None).zipped.map { case (alts, currLabel, nextLabel) =>
+            unfold(alts :+ bodyTm, currLabel, nextLabel)
           }
 
-          toHoist   = (for ((treeMakers, _) <- cases; tm <- treeMakers; hoisted <- tm.treesToHoist) yield hoisted).toList
+          if (caseDefs exists (_.isEmpty)) Nil
+          else caseDefs.flatten
+
+        case _ => Nil // failure
+      }
+
+      val caseDefs = cases map { makers =>
+        removeSubstOnly(makers) match {
+          // default case (don't move this to unfold, as it may only occur on the top level, not as an alternative -- well, except in degenerate matches)
+          case (btm@BodyTreeMaker(body, _)) :: Nil =>
+            List(CaseDef(Ident(nme.WILDCARD), EmptyTree, btm.substitution(body)))
+          case nonTrivialMakers =>
+            unfold(nonTrivialMakers)
+        }
+      }
 
-          pmgen.fun(scrutSym, combinedCases)
-        } else pmgen.zero
+      if (caseDefs exists (_.isEmpty)) None
+      else { import CODE._
+        val matcher = BLOCK(
+          VAL(scrutSym) === scrut, // TODO: type test for switchable type if patterns allow switch but the scrutinee doesn't
+          Match(REF(scrutSym), caseDefs.flatten) // match on scrutSym, not scrut to avoid duplicating scrut
+        )
 
+        // matcher filter (tree => tree.tpe == null) foreach println
+        // treeBrowser browse matcher
+        Some(matcher) // set type to avoid recursion in typedMatch
+      }
+    } else None
 
-      val expr = pmgen.runOrElse(scrut, matcher, scrutSym.info, if (isFullyDefined(pt)) pt else NoType)
-      if (toHoist isEmpty) expr
-      else Block(toHoist, expr)
+    def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] =
+      doCSE(prevBinder, doDCE(prevBinder, cases, pt), pt)
+
+    // calls propagateSubstitution on the treemakers
+    def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = fixerUpper(owner, scrut.pos){
+      val casesUnOpt = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them
+
+      emitSwitch(scrut, scrutSym, casesUnOpt, pt).getOrElse{
+        var toHoist = List[Tree]()
+        val matcher =
+          if (casesUnOpt nonEmpty) {
+            // when specified, need to propagate pt explicitly (type inferencer can't handle it)
+            val optPt =
+              if (isFullyDefined(pt)) inMatchMonad(pt)
+              else NoType
+
+            val cases =
+              if (optimizingCodeGen) optimizeCases(scrutSym, casesUnOpt, pt)
+              else casesUnOpt
+
+            val combinedCases =
+              cases.map(combineExtractors(_, pt)).reduceLeft(pmgen.typedOrElse(optPt))
+
+            toHoist = (for (treeMakers <- cases; tm <- treeMakers; hoisted <- tm.treesToHoist) yield hoisted).toList
+
+            pmgen.fun(scrutSym, combinedCases)
+          } else pmgen.zero
+
+
+        val expr = pmgen.runOrElse(scrut, matcher, scrutSym.info, if (isFullyDefined(pt)) pt else NoType)
+        if (toHoist isEmpty) expr
+        else Block(toHoist, expr)
+      }
     }
 
     // combineExtractors changes the current substitution's of the tree makers in `treeMakers`
     // requires propagateSubstitution(treeMakers) has been called
-    def combineExtractors(treeMakers: List[TreeMaker], body: Tree, pt: Type): Tree =
-      treeMakers.foldRight (body) (_.chainBefore(_, pt))
+    def combineExtractors(treeMakers: List[TreeMaker], pt: Type): Tree =
+      treeMakers.foldRight (EmptyTree: Tree) (_.chainBefore(_, pt))
+
+
+
+    // TODO: do this during tree construction, but that will require tracking the current owner in treemakers
+    // TODO: assign more fine-grained positions
+    // fixes symbol nesting, assigns positions
+    private def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser {
+      currentOwner = origOwner
+
+      override def traverse(t: Tree) {
+        if (t != EmptyTree && t.pos == NoPosition) {
+          t.setPos(pos)
+        }
+        t match {
+          case Function(_, _) if t.symbol == NoSymbol =>
+            t.symbol = currentOwner.newValue(t.pos, nme.ANON_FUN_NAME).setFlag(SYNTHETIC).setInfo(NoType)
+            // println("new symbol for "+ (t, t.symbol.ownerChain))
+          case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) =>
+            // println("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain))
+            t.symbol.owner = currentOwner
+          case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2)
+            // println("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain))
+            if(d.symbol.isLazy) { // for lazy val's accessor -- is there no tree??
+              assert(d.symbol.lazyAccessor != NoSymbol && d.symbol.lazyAccessor.owner == d.symbol.owner)
+              d.symbol.lazyAccessor.owner = currentOwner
+            }
+            if(d.symbol.moduleClass ne NoSymbol)
+              d.symbol.moduleClass.owner = currentOwner
 
+            d.symbol.owner = currentOwner
+          // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) =>
+          //   println("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain))
+          case _ =>
+        }
+        super.traverse(t)
+      }
+
+      // override def apply
+      // println("before fixerupper: "+ xTree)
+      // currentRun.trackerFactory.snapshot()
+      // println("after fixerupper")
+      // currentRun.trackerFactory.snapshot()
+    }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // substitution
@@ -1169,6 +1314,7 @@ defined class Foo */
       def fun(arg: Symbol, body: Tree): Tree
       def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree
       def zero: Tree
+      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree
       def condOptimized(c: Tree, then: Tree): Tree
       def _equals(checker: Tree, binder: Symbol): Tree
       def _asInstanceOf(b: Symbol, tp: Type): Tree
@@ -1176,6 +1322,7 @@ defined class Foo */
     }
 
     def pmgen: AbsCodeGen
+    def typed(tree: Tree, mode: Int, pt: Type): Tree // implemented in MatchTranslator
   }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
@@ -1391,49 +1538,6 @@ defined class Foo */
     }
 
     def matchingStrategy: Tree
-    def typed(tree: Tree, mode: Int, pt: Type): Tree // implemented in MatchTranslator
-  }
-
-
-  // TODO: do this during tree construction, but that will require tracking the current owner in treemakers
-  // TODO: assign more fine-grained positions
-  // fixes symbol nesting, assigns positions
-  def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser {
-    currentOwner = origOwner
-
-    override def traverse(t: Tree) {
-      if (t != EmptyTree && t.pos == NoPosition) {
-        t.setPos(pos)
-      }
-      t match {
-        case Function(_, _) if t.symbol == NoSymbol =>
-          t.symbol = currentOwner.newValue(t.pos, nme.ANON_FUN_NAME).setFlag(SYNTHETIC).setInfo(NoType)
-          // println("new symbol for "+ (t, t.symbol.ownerChain))
-        case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) =>
-          // println("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain))
-          t.symbol.owner = currentOwner
-        case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2)
-          // println("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain))
-          if(d.symbol.isLazy) { // for lazy val's accessor -- is there no tree??
-            assert(d.symbol.lazyAccessor != NoSymbol && d.symbol.lazyAccessor.owner == d.symbol.owner)
-            d.symbol.lazyAccessor.owner = currentOwner
-          }
-          if(d.symbol.moduleClass ne NoSymbol)
-            d.symbol.moduleClass.owner = currentOwner
-
-          d.symbol.owner = currentOwner
-        // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) =>
-        //   println("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain))
-        case _ =>
-      }
-      super.traverse(t)
-    }
-
-    // override def apply
-    // println("before fixerupper: "+ xTree)
-    // currentRun.trackerFactory.snapshot()
-    // println("after fixerupper")
-    // currentRun.trackerFactory.snapshot()
   }
 }
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 341e1bc5ea..f6f783516c 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -3223,9 +3223,19 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
             val owntype = elimAnonymousClass(owntype0)
             if (needAdapt) cases1 = cases1 map (adaptCase(_, owntype))
 
-            val translated = (new MatchTranslator(this)).translateMatch(selector1, cases1, owntype)
-
-            typed1(translated, mode, WildcardType) setType owntype // TODO: get rid of setType owntype -- it should all typecheck
+            (new MatchTranslator(this)).translateMatch(selector1, cases1, owntype) match {
+              case Block(vd :: Nil, tree@Match(selector, cases)) =>
+                val selector1 = checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType))
+                var cases1 = typedCases(tree, cases, packCaptured(selector1.tpe.widen), pt)
+                val (owntype, needAdapt) = ptOrLub(cases1 map (_.tpe))
+                if (needAdapt)
+                  cases1 = cases1 map (adaptCase(_, owntype))
+                typed(Block(vd :: Nil, treeCopy.Match(tree, selector1, cases1) setType owntype))
+              case translated =>
+                // TODO: get rid of setType owntype -- it should all typecheck
+                // must call typed, not typed1, or we overflow the stack when emitting switches
+                typed(translated, mode, WildcardType) setType owntype
+            }
           }
         }
       }
diff --git a/test/files/pos/virtpatmat_alts_subst.flags b/test/files/pos/virtpatmat_alts_subst.flags
new file mode 100644
index 0000000000..9769db9257
--- /dev/null
+++ b/test/files/pos/virtpatmat_alts_subst.flags
@@ -0,0 +1 @@
+ -Yvirtpatmat -Xexperimental
diff --git a/test/files/pos/virtpatmat_alts_subst.scala b/test/files/pos/virtpatmat_alts_subst.scala
new file mode 100644
index 0000000000..e27c52f9c7
--- /dev/null
+++ b/test/files/pos/virtpatmat_alts_subst.scala
@@ -0,0 +1,6 @@
+case class Foo(s: String) {
+  def appliedType(tycon: Any) =
+    tycon match {
+        case Foo(sym @ ("NothingClass" | "AnyClass")) => println(sym)
+    }
+}
diff --git a/test/files/pos/virtpatmat_binding_opt.flags b/test/files/pos/virtpatmat_binding_opt.flags
new file mode 100644
index 0000000000..9769db9257
--- /dev/null
+++ b/test/files/pos/virtpatmat_binding_opt.flags
@@ -0,0 +1 @@
+ -Yvirtpatmat -Xexperimental
diff --git a/test/files/pos/virtpatmat_binding_opt.scala b/test/files/pos/virtpatmat_binding_opt.scala
new file mode 100644
index 0000000000..962e3d7dbe
--- /dev/null
+++ b/test/files/pos/virtpatmat_binding_opt.scala
@@ -0,0 +1,11 @@
+class Test {
+  def combine = this match {
+    case that if that eq this => this // just return this
+    case that: Test2 =>
+      println(that)
+      this
+    case _ => error("meh")
+  }
+}
+
+class Test2 extends Test
\ No newline at end of file
diff --git a/test/files/run/virtpatmat_literal.scala b/test/files/run/virtpatmat_literal.scala
index cb72b1d2a5..5bd6b30791 100644
--- a/test/files/run/virtpatmat_literal.scala
+++ b/test/files/run/virtpatmat_literal.scala
@@ -1,8 +1,9 @@
 object Test extends App {
+ val a = 1
  1 match { 
    case 2 => println("FAILED") 
    case 1 => println("OK") 
-   case 1 => println("FAILED") 
+   case `a` => println("FAILED") 
  }
 
  val one = 1