Merge commit 'c58b240' into develop

3 files changed, 643 insertions, 644 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index b1e02cb062..6d31243fd0 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -7,8 +7,7 @@ package scala.tools.nsc
 package typechecker
 
 import symtab._
-import Flags.{ CASE => _, _ }
-
+import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC}
 
 /** Translate pattern matching into method calls (these methods form a zero-plus monad), similar in spirit to how for-comprehensions are compiled.
   *
@@ -16,29 +15,16 @@ import Flags.{ CASE => _, _ }
   * (lifting the body of the case into the monad using `one`).
   *
   * Cases are combined into a pattern match using the `orElse` combinator (the implicit failure case is expressed using the monad's `zero`).
-  *
-  * The monad `M` in which the pattern match is interpreted is determined by solving `implicitly[MatchingStrategy[M]]` for M.
-  * Predef provides the default, `OptionMatching`
-
-  * Example translation: TODO
-
-    scrut match { case Person(father@Person(_, fatherName), name) if fatherName == name => }
-    scrut match { case Person(father, name) => father match {case Person(_, fatherName) => }}
-    Person.unapply(scrut) >> ((father, name) => (Person.unapply(father) >> (_, fatherName) => check(fatherName == name) >> (_ => body)))
-
-    (a => (Person.unapply(a).>>(
-      b => Person.unapply(b._1).>>(
-        c => check(c._2 == b._2).>>(
-          d => body)))))(scrut)
-
-TODO:
- - optimizer loops on virtpatmat compiler?
-
- - don't orElse a failure case at the end if there's a default case
- - implement spec more closely (see TODO's below)
- - fix inlining of methods in nested objects
 
+  * TODO:
+  *  - interaction with CPS
+  *  - Array patterns
+  *  - implement spec more closely (see TODO's)
+  *  - DCE
+  *  - use manifests for type testing
+  *
   * (longer-term) TODO:
+  *  - user-defined unapplyProd
   *  - recover GADT typing by locally inserting implicit witnesses to type equalities derived from the current case, and considering these witnesses during subtyping (?)
   *  - recover exhaustivity and unreachability checking using a variation on the type-safe builder pattern
   */
@@ -46,26 +32,90 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
   import global._
   import definitions._
 
-  class MatchTranslator(typer: Typer) extends MatchCodeGen {
-    def typed(tree: Tree, mode: Int, pt: Type): Tree = typer.typed(tree, mode, pt) // for MatchCodeGen -- imports don't provide implementations for abstract members
+  object vpmName {
+    val one       = newTermName("one")
+    val drop      = newTermName("drop")
+    val flatMap   = newTermName("flatMap")
+    val get       = newTermName("get")
+    val guard     = newTermName("guard")
+    val isEmpty   = newTermName("isEmpty")
+    val orElse    = newTermName("orElse")
+    val outer     = newTermName("<outer>")
+    val runOrElse = newTermName("runOrElse")
+    val zero      = newTermName("zero")
+    val __match   = newTermName("__match")
+
+    def counted(str: String, i: Int) = newTermName(str+i)
+  }
+
+  object MatchTranslator {
+    def apply(typer: Typer): MatchTranslation = {
+      import typer._
+      // typing `__match` to decide which MatchTranslator to create adds 4% to quick.comp.timer
+      newTyper(context.makeImplicit(reportAmbiguousErrors = false)).silent(_.typed(Ident(vpmName.__match), EXPRmode, WildcardType), reportAmbiguousErrors = false) match {
+          case SilentResultValue(ms) => new PureMatchTranslator(typer, ms)
+          case _ => new OptimizingMatchTranslator(typer)
+        }
+    }
+  }
 
-    import typer._
-    import typeDebug.{ ptTree, ptBlock, ptLine }
+  class PureMatchTranslator(val typer: Typer, val matchStrategy: Tree) extends MatchTranslation with TreeMakers with PureCodegen
+  class OptimizingMatchTranslator(val typer: Typer)                    extends MatchTranslation with TreeMakers with MatchOptimizations
 
-    def solveContextBound(contextBoundTp: Type): (Tree, Type) = {
-      val solSym      = NoSymbol.newTypeParameter(newTypeName("SolveImplicit$"))
-      val param       = solSym.setInfo(contextBoundTp.typeSymbol.typeParams(0).info.cloneInfo(solSym)) // TypeBounds(NothingClass.typeConstructor, baseTp)
-      val pt          = appliedType(contextBoundTp, List(param.tpeHK))
-      val savedUndets = context.undetparams
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// talking to userland
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
-      context.undetparams = param :: context.undetparams
-      val result          = inferImplicit(EmptyTree, pt, false, false, context)
-      context.undetparams = savedUndets
+  /** Interface with user-defined match monad?
+   * if there's a `__match` in scope, we use this as the match strategy, assuming it conforms to MatchStrategy as defined below:
+
+       type Matcher[P[_], M[+_], A] = {
+         def flatMap[B](f: P[A] => M[B]): M[B]
+         def orElse[B >: A](alternative: => M[B]): M[B]
+       }
+
+       abstract class MatchStrategy[P[_], M[+_]] {
+         // runs the matcher on the given input
+         def runOrElse[T, U](in: P[T])(matcher: P[T] => M[U]): P[U]
+
+         def zero: M[Nothing]
+         def one[T](x: P[T]): M[T]
+         def guard[T](cond: P[Boolean], then: => P[T]): M[T]
+         def isSuccess[T, U](x: P[T])(f: P[T] => M[U]): P[Boolean] // used for isDefinedAt
+       }
+
+   * P and M are derived from one's signature (`def one[T](x: P[T]): M[T]`)
+
+
+   * if no `__match` is found, we assume the following implementation (and generate optimized code accordingly)
+
+       object __match extends MatchStrategy[({type Id[x] = x})#Id, Option] {
+         def zero = None
+         def one[T](x: T) = Some(x)
+         // NOTE: guard's return type must be of the shape M[T], where M is the monad in which the pattern match should be interpreted
+         def guard[T](cond: Boolean, then: => T): Option[T] = if(cond) Some(then) else None
+         def runOrElse[T, U](x: T)(f: T => Option[U]): U = f(x) getOrElse (throw new MatchError(x))
+         def isSuccess[T, U](x: T)(f: T => Option[U]): Boolean = !f(x).isEmpty
+       }
+
+   */
+  trait MatchMonadInterface {
+    val typer: Typer
+    val matchOwner = typer.context.owner
+
+    def inMatchMonad(tp: Type): Type
+    def pureType(tp: Type): Type
+    final def matchMonadResult(tp: Type): Type =
+      tp.baseType(matchMonadSym).typeArgs match {
+        case arg :: Nil => arg
+        case _ => ErrorType
+      }
 
-      (result.tree, result.subst.to(result.subst.from indexOf param))
-    }
+    protected def matchMonadSym: Symbol
+  }
 
-    lazy val (matchingStrategy, matchingMonadType) = solveContextBound(MatchingStrategyClass.typeConstructor)
+  trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore =>
+    import typer.{typed, context, silent, reallyExists}
 
     /** Implement a pattern match by turning its cases (including the implicit failure case)
       * into the corresponding (monadic) extractors, and combining them with the `orElse` combinator.
@@ -75,7 +125,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       *
       * NOTE: the resulting tree is not type checked, nor are nested pattern matches transformed
       *   thus, you must typecheck the result (and that will in turn translate nested matches)
-      *   this could probably optimized... (but note that the matchingStrategy must be solved for each nested patternmatch)
+      *   this could probably optimized... (but note that the matchStrategy must be solved for each nested patternmatch)
       */
     def translateMatch(scrut: Tree, cases: List[CaseDef], pt: Type): Tree = {
       // we don't transform after typers
@@ -83,12 +133,17 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       //  and the only place that emits Matches after typers is for exception handling anyway)
       assert(phase.id <= currentRun.typerPhase.id, phase)
 
+      def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match {
+        case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args)
+        case _ => tp
+      }
+
       val scrutType = repeatedToSeq(elimAnonymousClass(scrut.tpe.widen))
 
-      val scrutSym  = freshSym(scrut.pos, scrutType)
+      val scrutSym  = freshSym(scrut.pos, pureType(scrutType))
       val okPt = repeatedToSeq(pt)
       // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala  with -Xexperimental
-      combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, context.owner)
+      combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, matchOwner)
     }
 
 
@@ -139,6 +194,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         // must use type `tp`, which is provided by extractor's result, not the type expected by binder,
         // as b.info may be based on a Typed type ascription, which has not been taken into account yet by the translation
         // (it will later result in a type test when `tp` is not a subtype of `b.info`)
+        // TODO: can we simplify this, together with the Bound case?
         (extractor.subPatBinders, extractor.subPatTypes).zipped foreach { case (b, tp) => b setInfo tp } // println("changing "+ b +" : "+ b.info +" -> "+ tp);
 
         // println("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType))
@@ -215,12 +271,8 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
             and it binds the variable name to that value.
         **/
         case Bound(subpatBinder, p)          =>
-          // TreeMaker with empty list of trees only performs the substitution subpatBinder --> patBinder
-          // println("rebind "+ subpatBinder +" to "+ patBinder)
-          withSubPats(List(SubstOnlyTreeMaker(Substitution(subpatBinder, CODE.REF(patBinder)))),
-            // the symbols are markers that may be used to refer to the result of the extractor in which the corresponding tree is nested
-            // it's the responsibility of the treemaker to replace this symbol by a reference that
-            // selects that result on the function symbol of the flatMap call that binds to the result of this extractor
+          // replace subpatBinder by patBinder (as if the Bind was not there)
+          withSubPats(List(SubstOnlyTreeMaker(subpatBinder, patBinder)),
             // must be patBinder, as subpatBinder has the wrong info: even if the bind assumes a better type, this is not guaranteed until we cast
             (patBinder, p)
           )
@@ -266,7 +318,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       if (guard == EmptyTree) Nil
       else List(GuardTreeMaker(guard))
 
-    // TODO: 1) if we want to support a generalisation of Kotlin's patmat continue, must not hard-wire lifting into the monad (which is now done by pmgen.one),
+    // TODO: 1) if we want to support a generalisation of Kotlin's patmat continue, must not hard-wire lifting into the monad (which is now done by codegen.one),
     // so that user can generate failure when needed -- use implicit conversion to lift into monad on-demand?
     // to enable this, probably need to move away from Option to a monad specific to pattern-match,
     // 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
@@ -379,34 +431,32 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       protected lazy val expectedLength      = lastIndexingBinder - firstIndexingBinder + 1
       protected lazy val minLenToCheck       = if(lastIsStar) 1 else 0
       protected def seqTree(binder: Symbol)  = tupleSel(binder)(firstIndexingBinder+1)
-      protected def tupleSel(binder: Symbol)(i: Int): Tree = pmgen.tupleSel(binder)(i)
+      protected def tupleSel(binder: Symbol)(i: Int): Tree = codegen.tupleSel(binder)(i)
 
       // the trees that select the subpatterns on the extractor's result, referenced by `binder`
       // require isSeq
       protected def subPatRefsSeq(binder: Symbol): List[Tree] = {
-        // only relevant if isSeq: (here to avoid capturing too much in the returned closure)
-        val indexingIndices               = (0 to (lastIndexingBinder-firstIndexingBinder))
-        val nbIndexingIndices             = indexingIndices.length
+        val indexingIndices   = (0 to (lastIndexingBinder-firstIndexingBinder))
+        val nbIndexingIndices = indexingIndices.length
 
-        // this error is checked by checkStarPatOK
-        // if(isSeq) assert(firstIndexingBinder + nbIndexingIndices + (if(lastIsStar) 1 else 0) == nbSubPats, "(resultInMonad, ts, subPatTypes, subPats)= "+(resultInMonad, ts, subPatTypes, subPats))
+        // this error-condition has already been checked by checkStarPatOK:
+        //   if(isSeq) assert(firstIndexingBinder + nbIndexingIndices + (if(lastIsStar) 1 else 0) == nbSubPats, "(resultInMonad, ts, subPatTypes, subPats)= "+(resultInMonad, ts, subPatTypes, subPats))
         // there are `firstIndexingBinder` non-seq tuple elements preceding the Seq
         (((1 to firstIndexingBinder) map tupleSel(binder)) ++
         // then we have to index the binder that represents the sequence for the remaining subpatterns, except for...
-        (indexingIndices map pmgen.index(seqTree(binder))) ++
+        (indexingIndices map codegen.index(seqTree(binder))) ++
         // the last one -- if the last subpattern is a sequence wildcard: drop the prefix (indexed by the refs on the line above), return the remainder
         (if(!lastIsStar) Nil else List(
           if(nbIndexingIndices == 0) seqTree(binder)
-          else pmgen.drop(seqTree(binder))(nbIndexingIndices)))).toList
+          else codegen.drop(seqTree(binder))(nbIndexingIndices)))).toList
       }
 
       // the trees that select the subpatterns on the extractor's result, referenced by `binder`
       // require (nbSubPats > 0 && (!lastIsStar || isSeq))
-      protected def subPatRefs(binder: Symbol): List[Tree] = {
+      protected def subPatRefs(binder: Symbol): List[Tree] =
         if (nbSubPats == 0) Nil
         else if (isSeq) subPatRefsSeq(binder)
         else ((1 to nbSubPats) map tupleSel(binder)).toList
-      }
 
       protected def lengthGuard(binder: Symbol): Option[Tree] =
         // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied
@@ -427,7 +477,9 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         }
     }
 
-    // TODO: to be called when there's a def unapplyProd(x: T): Product_N
+    // TODO: to be called when there's a def unapplyProd(x: T): U
+    // U must have N members _1,..., _N -- the _i are type checked, call their type Ti,
+    //
     // for now only used for case classes -- pretending there's an unapplyProd that's the identity (and don't call it)
     class ExtractorCallProd(fun: Tree, args: List[Tree]) extends ExtractorCall(args) {
       // TODO: fix the illegal type bound in pos/t602 -- type inference messes up before we get here:
@@ -439,15 +491,15 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       // private val extractorTp     = if (wellKinded(fun.tpe)) fun.tpe else existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType)
       // println("ExtractorCallProd: "+ (fun.tpe, existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType)))
       // println("ExtractorCallProd: "+ (fun.tpe, args map (_.tpe)))
-      private def extractorTp = fun.tpe
+      private def constructorTp = fun.tpe
 
       def isTyped    = fun.isTyped
 
       // to which type should the previous binder be casted?
-      def paramType  = extractorTp.finalResultType
+      def paramType  = constructorTp.finalResultType
 
       def isSeq: Boolean = rawSubPatTypes.nonEmpty && isRepeatedParamType(rawSubPatTypes.last)
-      protected def rawSubPatTypes = extractorTp.paramTypes
+      protected def rawSubPatTypes = constructorTp.paramTypes
 
       // binder has type paramType
       def treeMaker(binder: Symbol, pos: Position): TreeMaker = {
@@ -456,31 +508,20 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       }
 
 /* TODO: remove special case when the following bug is fixed
-scala> :paste
-// Entering paste mode (ctrl-D to finish)
-
 class Foo(x: Other) { x._1 } // BUG: can't refer to _1 if its defining class has not been type checked yet
 case class Other(y: String)
-
-// Exiting paste mode, now interpreting.
-
-<console>:8: error: value _1 is not a member of Other
-       class Foo(x: Other) { x._1 }
-                               ^
-
-scala> case class Other(y: String)
-defined class Other
-
-scala> class Foo(x: Other) { x._1 }
-defined class Foo */
+-- this is ok:
+case class Other(y: String)
+class Foo(x: Other) { x._1 } // no error in this order
+*/
       override protected def tupleSel(binder: Symbol)(i: Int): Tree = { import CODE._
         // reference the (i-1)th case accessor if it exists, otherwise the (i-1)th tuple component
         val caseAccs = binder.info.typeSymbol.caseFieldAccessors
         if (caseAccs isDefinedAt (i-1)) REF(binder) DOT caseAccs(i-1)
-        else pmgen.tupleSel(binder)(i)
+        else codegen.tupleSel(binder)(i)
       }
 
-      override def toString(): String = "case class "+ (if (extractorTp eq null) fun else paramType.typeSymbol) +" with arguments "+ args
+      override def toString(): String = "case class "+ (if (constructorTp eq null) fun else paramType.typeSymbol) +" with arguments "+ args
     }
 
     class ExtractorCallRegular(extractorCallIncludingDummy: Tree, args: List[Tree]) extends ExtractorCall(args) {
@@ -495,7 +536,7 @@ defined class Foo */
       def treeMaker(patBinderOrCasted: Symbol, pos: Position): TreeMaker = {
         // the extractor call (applied to the binder bound by the flatMap corresponding to the previous (i.e., enclosing/outer) pattern)
         val extractorApply = atPos(pos)(spliceApply(patBinderOrCasted))
-        val binder         = freshSym(pos, resultInMonad) // can't simplify this when subPatBinders.isEmpty, since UnitClass.tpe is definitely wrong when isSeq, and resultInMonad should always be correct since it comes directly from the extractor's result type
+        val binder         = freshSym(pos, pureType(resultInMonad)) // can't simplify this when subPatBinders.isEmpty, since UnitClass.tpe is definitely wrong when isSeq, and resultInMonad should always be correct since it comes directly from the extractor's result type
         ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder, Substitution(subPatBinders, subPatRefs(binder)))(resultType.typeSymbol == BooleanClass)
       }
 
@@ -524,12 +565,7 @@ defined class Foo */
       // turn an extractor's result type into something `monadTypeToSubPatTypesAndRefs` understands
       protected lazy val resultInMonad: Type = if(!hasLength(tpe.paramTypes, 1)) ErrorType else {
         if (resultType.typeSymbol == BooleanClass) UnitClass.tpe
-        else {
-          val monadArgs = resultType.baseType(matchingMonadType.typeSymbol).typeArgs
-          // assert(monadArgs.length == 1, "unhandled extractor type: "+ extractorTp) // TODO: overloaded unapply??
-          if(monadArgs.length == 1) monadArgs(0)
-          else ErrorType
-        }
+        else matchMonadResult(resultType)
       }
 
       protected lazy val rawSubPatTypes =
@@ -543,81 +579,6 @@ defined class Foo */
       override def toString() = extractorCall +": "+ extractorCall.tpe +" (symbol= "+ extractorCall.symbol +")."
     }
 
-    // tack an outer test onto `cond` if binder.info and expectedType warrant it
-    def maybeWithOuterCheck(binder: Symbol, expectedTp: Type)(cond: Tree): Tree = { import CODE._
-      if (   !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
-          && needsOuterTest(expectedTp, binder.info, context.owner)) {
-        val expectedPrefix = expectedTp.prefix match {
-          case ThisType(clazz)  => THIS(clazz)
-          case pre              => REF(pre.prefix, pre.termSymbol)
-        }
-
-        // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix`
-        // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor?
-        val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC
-        val outerCheck = (Select(pmgen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix
-
-        // first check cond, since that should ensure we're not selecting outer on null
-        pmgen.and(cond, outerCheck)
-      }
-      else
-        cond
-    }
-
-    // TODO: also need to test when erasing pt loses crucial information (and if we can recover it using a manifest)
-    def needsTypeTest(tp: Type, pt: Type) = !(tp <:< pt)
-    def typeTest(binder: Symbol, pt: Type) = maybeWithOuterCheck(binder, pt)(pmgen._isInstanceOf(binder, pt))
-
-    /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms:
-        - A reference to a class C, p.C, or T#C.
-          This type pattern matches any non-null instance of the given class.
-          Note that the prefix of the class, if it is given, is relevant for determining class instances.
-          For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix.
-          The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case.
-
-        - A singleton type p.type.
-          This type pattern matches only the value denoted by the path p
-          (that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now
-          // https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time"
-
-        - A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern.
-          This type pattern matches all values that are matched by each of the type patterns Ti.
-
-        - A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _.
-          This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards.
-          The bounds or alias type of these type variable are determined as described in (§8.3).
-
-        - A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO
-          This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1.
-    **/
-
-    // generate the tree for the run-time test that follows from the fact that
-    // a `scrut` of known type `scrutTp` is expected to have type `expectedTp`
-    // uses maybeWithOuterCheck to check the type's prefix
-    def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree = { import CODE._
-       // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null`
-       // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false")
-      def genEqualsAndInstanceOf(sym: Symbol): Tree
-        = pmgen._equals(REF(sym), patBinder) AND pmgen._isInstanceOf(patBinder, pt.widen)
-
-      def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe
-
-      val patBinderTp = patBinder.info.widen
-      def isMatchUnlessNull = isRefTp(pt) && !needsTypeTest(patBinderTp, pt)
-
-      // TODO: [SPEC] type test for Array
-      // TODO: use manifests to improve tests (for erased types we can do better when we have a manifest)
-      pt match {
-          case SingleType(_, sym) /*this implies sym.isStable*/ => genEqualsAndInstanceOf(sym) // TODO: [SPEC] the spec requires `eq` instead of `==` here
-          case ThisType(sym) if sym.isModule                    => genEqualsAndInstanceOf(sym) // must use == to support e.g. List() == Nil
-          case ThisType(sym)                                    => REF(patBinder) OBJ_EQ This(sym)
-          case ConstantType(Constant(null)) if isRefTp(patBinderTp) => REF(patBinder) OBJ_EQ NULL
-          case ConstantType(const)                              => pmgen._equals(Literal(const), patBinder)
-          case _ if isMatchUnlessNull                           => maybeWithOuterCheck(patBinder, pt)(REF(patBinder) OBJ_NE NULL)
-          case _                                                => typeTest(patBinder, pt)
-        }
-    }
-
     /** A conservative approximation of which patterns do not discern anything.
      * They are discarded during the translation.
      */
@@ -643,14 +604,74 @@ defined class Foo */
   }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// substitution
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  trait TypedSubstitution extends MatchMonadInterface {
+    object Substitution {
+      def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
+      // requires sameLength(from, to)
+      def apply(from: List[Symbol], to: List[Tree]) =
+        if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
+    }
+
+    class Substitution(val from: List[Symbol], val to: List[Tree]) {
+      // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
+      // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
+      def apply(tree: Tree): Tree = {
+        // according to -Ystatistics 10% of translateMatch's time is spent in this method...
+        // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
+        if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
+        else (new Transformer {
+          @inline private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
+            if (origTp == null || origTp == NoType) to
+            // important: only type when actually substing and when original tree was typed
+            // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
+            else typer.typed(to, EXPRmode, WildcardType)
+
+          override def transform(tree: Tree): Tree = {
+            def subst(from: List[Symbol], to: List[Tree]): Tree =
+              if (from.isEmpty) tree
+              else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate, tree.tpe)
+              else subst(from.tail, to.tail)
+
+            tree match {
+              case Ident(_) => subst(from, to)
+              case _        => super.transform(tree)
+            }
+          }
+        }).transform(tree)
+      }
+
+
+      // the substitution that chains `other` before `this` substitution
+      // forall t: Tree. this(other(t)) == (this >> other)(t)
+      def >>(other: Substitution): Substitution = {
+        val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) =>  !other.from.contains(f) }
+        new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
+      }
+      override def toString = (from zip to) mkString("Substitution(", ", ", ")")
+    }
+
+    object EmptySubstitution extends Substitution(Nil, Nil) {
+      override def apply(tree: Tree): Tree = tree
+      override def >>(other: Substitution): Substitution = other
+    }
+  }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // the making of the trees
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  trait TreeMakers extends TypedSubstitution { self: CodegenCore =>
+    def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) =
+      (cases, Nil)
 
-  trait TreeMakers {
-    def inMatchMonad(tp: Type): Type = appliedType(matchingMonadType, List(tp))
-    lazy val optimizingCodeGen       = matchingMonadType.typeSymbol eq OptionClass
+    def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] =
+      None
 
     abstract class TreeMaker {
+      /** captures the scope and the value of the bindings in patterns
+       * important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed)
+       */
       def substitution: Substitution =
         if (currSub eq null) localSubstitution
         else currSub
@@ -668,7 +689,6 @@ defined class Foo */
 
       // build Tree that chains `next` after the current extractor
       def chainBefore(next: Tree, pt: Type): Tree
-      def treesToHoist: List[Tree] = Nil
     }
 
     case class TrivialTreeMaker(tree: Tree) extends TreeMaker {
@@ -679,71 +699,30 @@ defined class Foo */
     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
+        atPos(body.pos)(substitution(codegen.one(body, body.tpe, matchPt))) // since SubstOnly treemakers are dropped, need to do it here
     }
 
-    case class SubstOnlyTreeMaker(localSubstitution: Substitution) extends TreeMaker {
+    case class SubstOnlyTreeMaker(prevBinder: Symbol, nextBinder: Symbol) extends TreeMaker {
+      val localSubstitution = Substitution(prevBinder, CODE.REF(nextBinder))
       def chainBefore(next: Tree, pt: Type): Tree = substitution(next)
     }
 
     abstract class FunTreeMaker extends TreeMaker {
       val nextBinder: Symbol
-
-      // for CSE (used iff optimizingCodeGen)
-      // TODO: factor this out -- don't mutate treemakers
-      var reused: Boolean = false
-      def reusedBinders: List[Symbol] = Nil
-      override def treesToHoist: List[Tree] = { import CODE._
-        reusedBinders map { b => VAL(b) === pmgen.mkZero(b.info) }
-      }
     }
 
-    abstract class FreshFunTreeMaker extends FunTreeMaker {
+    abstract class CondTreeMaker extends FunTreeMaker {
       val pos: Position
       val prevBinder: Symbol
       val nextBinderTp: Type
-      lazy val nextBinder = freshSym(pos, nextBinderTp)
-      lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
-    }
-
-    // TODO: factor out optimization-specific stuff into codegen
-    abstract class CondTreeMaker extends FreshFunTreeMaker { import CODE._
       val cond: Tree
       val res: Tree
 
-      // for CSE (used iff optimizingCodeGen)
-      // must set reused before!
-      override lazy val reusedBinders = if(reused) List(freshSym(pos, BooleanClass.tpe, "rc") setFlag MUTABLE, nextBinder setFlag MUTABLE) else Nil
-      def storedCond         = reusedBinders(0)
-      def storedRes          = reusedBinders(1)
+      lazy val nextBinder = freshSym(pos, nextBinderTp)
+      lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
 
       def chainBefore(next: Tree, pt: Type): Tree =
-        if (!reused)
-          atPos(pos)(pmgen.flatMapCond(cond, res, nextBinder, nextBinderTp, substitution(next)))
-        else { // for CSE (used iff optimizingCodeGen)
-          IF (cond) THEN BLOCK(
-            storedCond === TRUE,
-            storedRes  === res,
-            substitution(next).duplicate // TODO: finer-grained dup'ing
-          ) ELSE pmgen.zero
-        }
-    }
-
-    // for CSE (used iff optimizingCodeGen)
-    case class ReusingCondTreeMaker(dropped_priors: List[(TreeMaker, Option[TreeMaker])]) extends TreeMaker { import CODE._
-      lazy val localSubstitution = {
-        val (from, to) = dropped_priors.collect {case (dropped: CondTreeMaker, Some(prior: CondTreeMaker)) => (dropped.nextBinder, REF(prior.storedRes))}.unzip
-        val oldSubs = dropped_priors.collect {case (dropped: TreeMaker, _) => dropped.substitution}
-        oldSubs.foldLeft(Substitution(from, to))(_ >> _)
-      }
-
-      def chainBefore(next: Tree, pt: Type): Tree = {
-        val cond = REF(dropped_priors.reverse.collectFirst{case (_, Some(ctm: CondTreeMaker)) => ctm}.get.storedCond)
-
-        IF (cond) THEN BLOCK(
-          substitution(next).duplicate // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift, and its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S)
-        ) ELSE pmgen.zero
-      }
+        atPos(pos)(codegen.flatMapCond(cond, res, nextBinder, nextBinderTp, substitution(next)))
     }
 
     /**
@@ -754,12 +733,13 @@ defined class Foo */
      * in this function's body, and all the subsequent ones, references to the symbols in `from` will be replaced by the corresponding tree in `to`
      */
     case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol, localSubstitution: Substitution)(extractorReturnsBoolean: Boolean) extends FunTreeMaker {
-      def chainBefore(next: Tree, pt: Type): Tree = atPos(extractor.pos)(
-        if (extractorReturnsBoolean) pmgen.flatMapCond(extractor, CODE.UNIT, nextBinder, nextBinder.info.widen, substitution(condAndNext(next)))
-        else pmgen.flatMap(extractor, pmgen.fun(nextBinder, substitution(condAndNext(next))))
-      )
-
-      private def condAndNext(next: Tree): Tree = extraCond map (pmgen.condOptimized(_, next)) getOrElse next
+      def chainBefore(next: Tree, pt: Type): Tree = {
+        val condAndNext = extraCond map (codegen.ifThenElseZero(_, next)) getOrElse next
+        atPos(extractor.pos)(
+          if (extractorReturnsBoolean) codegen.flatMapCond(extractor, CODE.UNIT, nextBinder, nextBinder.info.widen, substitution(condAndNext))
+          else codegen.flatMap(extractor, nextBinder, substitution(condAndNext))
+        )
+      }
 
       override def toString = "X"+(extractor, nextBinder)
     }
@@ -768,21 +748,42 @@ defined class Foo */
     case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends TreeMaker { import CODE._
       def chainBefore(next: Tree, pt: Type): Tree = {
         val nullCheck = REF(prevBinder) OBJ_NE NULL
-        val cond = extraCond match {
-          case None => nullCheck
-          case Some(c) => nullCheck AND c
-        }
-        pmgen.condOptimized(cond, substitution(next))
+        val cond = extraCond map (nullCheck AND _) getOrElse nullCheck
+        codegen.ifThenElseZero(cond, substitution(next))
       }
 
       override def toString = "P"+(prevBinder,  extraCond getOrElse "", localSubstitution)
     }
 
+    // tack an outer test onto `cond` if binder.info and expectedType warrant it
+    def maybeWithOuterCheck(binder: Symbol, expectedTp: Type)(cond: Tree): Tree = { import CODE._
+      if (   !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
+          && needsOuterTest(expectedTp, binder.info, matchOwner)) {
+        val expectedPrefix = expectedTp.prefix match {
+          case ThisType(clazz)  => THIS(clazz)
+          case pre              => REF(pre.prefix, pre.termSymbol)
+        }
+
+        // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix`
+        // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor?
+        val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC
+        val outerCheck = (Select(codegen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix
+
+        // first check cond, since that should ensure we're not selecting outer on null
+        codegen.and(cond, outerCheck)
+      }
+      else
+        cond
+    }
+
+    // TODO: also need to test when erasing pt loses crucial information (and if we can recover it using a manifest)
+    def needsTypeTest(tp: Type, pt: Type) = !(tp <:< pt)
+    private def typeTest(binder: Symbol, pt: Type) = maybeWithOuterCheck(binder, pt)(codegen._isInstanceOf(binder, pt))
 
     // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case)
     case class TypeTestTreeMaker(prevBinder: Symbol, nextBinderTp: Type, pos: Position) extends CondTreeMaker {
       val cond = typeTest(prevBinder, nextBinderTp)
-      val res  = pmgen._asInstanceOf(prevBinder, nextBinderTp)
+      val res  = codegen._asInstanceOf(prevBinder, nextBinderTp)
       override def toString = "TT"+(prevBinder, nextBinderTp)
     }
 
@@ -790,8 +791,58 @@ defined class Foo */
     case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends CondTreeMaker {
       val nextBinderTp = glb(List(patBinder.info.widen, pt))
 
+      /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms:
+          - A reference to a class C, p.C, or T#C.
+            This type pattern matches any non-null instance of the given class.
+            Note that the prefix of the class, if it is given, is relevant for determining class instances.
+            For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix.
+            The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case.
+
+          - A singleton type p.type.
+            This type pattern matches only the value denoted by the path p
+            (that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now
+            // https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time"
+
+          - A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern.
+            This type pattern matches all values that are matched by each of the type patterns Ti.
+
+          - A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _.
+            This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards.
+            The bounds or alias type of these type variable are determined as described in (§8.3).
+
+          - A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO
+            This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1.
+      **/
+
+      // generate the tree for the run-time test that follows from the fact that
+      // a `scrut` of known type `scrutTp` is expected to have type `expectedTp`
+      // uses maybeWithOuterCheck to check the type's prefix
+      private def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree = { import CODE._
+         // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null`
+         // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false")
+        def genEqualsAndInstanceOf(sym: Symbol): Tree
+          = codegen._equals(REF(sym), patBinder) AND codegen._isInstanceOf(patBinder, pt.widen)
+
+        def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe
+
+        val patBinderTp = patBinder.info.widen
+        def isMatchUnlessNull = isRefTp(pt) && !needsTypeTest(patBinderTp, pt)
+
+        // TODO: [SPEC] type test for Array
+        // TODO: use manifests to improve tests (for erased types we can do better when we have a manifest)
+        pt match {
+            case SingleType(_, sym) /*this implies sym.isStable*/ => genEqualsAndInstanceOf(sym) // TODO: [SPEC] the spec requires `eq` instead of `==` here
+            case ThisType(sym) if sym.isModule                    => genEqualsAndInstanceOf(sym) // must use == to support e.g. List() == Nil
+            case ThisType(sym)                                    => REF(patBinder) OBJ_EQ This(sym)
+            case ConstantType(Constant(null)) if isRefTp(patBinderTp) => REF(patBinder) OBJ_EQ NULL
+            case ConstantType(const)                              => codegen._equals(Literal(const), patBinder)
+            case _ if isMatchUnlessNull                           => maybeWithOuterCheck(patBinder, pt)(REF(patBinder) OBJ_NE NULL)
+            case _                                                => typeTest(patBinder, pt)
+          }
+      }
+
       val cond = typeAndEqualityTest(patBinder, pt)
-      val res  = pmgen._asInstanceOf(patBinder, nextBinderTp)
+      val res  = codegen._asInstanceOf(patBinder, nextBinderTp)
       override def toString = "TET"+(patBinder, pt)
     }
 
@@ -801,7 +852,7 @@ defined class Foo */
 
       // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null)
       // equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required)
-      val cond = pmgen._equals(patTree, prevBinder)
+      val cond = codegen._equals(patTree, prevBinder)
       val res  = CODE.REF(prevBinder)
       override def toString = "ET"+(prevBinder, patTree)
     }
@@ -836,7 +887,7 @@ defined class Foo */
           if (canDuplicate) {
             altss map {altTreeMakers =>
               combineExtractors(altTreeMakers :+ TrivialTreeMaker(substitution(next).duplicate), pt)
-            } reduceLeft pmgen.typedOrElse(pt)
+            } reduceLeft codegen.typedOrElse(pt)
           } else {
             val rest = freshSym(pos, functionType(List(), inMatchMonad(pt)), "rest")
             // rest.info.member(nme.apply).withAnnotation(AnnotationInfo(ScalaInlineClass.tpe, Nil, Nil))
@@ -848,7 +899,7 @@ defined class Foo */
             )
             BLOCK(
               VAL(rest) === Function(Nil, substitution(next)),
-              combinedAlts reduceLeft pmgen.typedOrElse(pt)
+              combinedAlts reduceLeft codegen.typedOrElse(pt)
             )
           }
         )
@@ -857,14 +908,239 @@ defined class Foo */
 
     case class GuardTreeMaker(guardTree: Tree) extends TreeMaker {
       val localSubstitution: Substitution = EmptySubstitution
-      def chainBefore(next: Tree, pt: Type): Tree = pmgen.flatMapGuard(substitution(guardTree), next)
+      def chainBefore(next: Tree, pt: Type): Tree = codegen.flatMapGuard(substitution(guardTree), next)
       override def toString = "G("+ guardTree +")"
     }
 
+    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
+      }
+      removeSubstOnly(treeMakers)
+    }
+
+    // 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{
+        val (matcher, hasDefault, toHoist) =
+          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
+
+            // do this check on casesUnOpt, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one
+            // exhaustivity and reachability must be checked before optimization as well
+            val hasDefault = casesUnOpt.nonEmpty && {
+              val nonTrivLast = casesUnOpt.last
+              nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
+            }
+
+            val (cases, toHoist) = optimizeCases(scrutSym, casesUnOpt, pt)
+
+            val combinedCases =
+              cases.map(combineExtractors(_, pt)).reduceLeft(codegen.typedOrElse(optPt))
+
+            (combinedCases, hasDefault, toHoist)
+          } else (codegen.zero, false, Nil)
+
+        val expr = codegen.runOrElse(scrut, scrutSym, matcher, if (isFullyDefined(pt)) pt else NoType, hasDefault)
+        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], 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.newAnonymousFunctionValue(t.pos)
+            // 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)
+              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()
+    }
+  }
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// generate actual trees
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  trait CodegenCore extends MatchMonadInterface {
+    private var ctr = 0
+    def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x") = {ctr += 1;
+      // assert(owner ne null)
+      // assert(owner ne NoSymbol)
+      NoSymbol.newTermSymbol(vpmName.counted(prefix, ctr), pos) setInfo repackExistential(tp)
+    }
+
+    // codegen relevant to the structure of the translation (how extractors are combined)
+    trait AbsCodegen {
+      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): Tree
+      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree
+      def zero: Tree
+      def flatMap(prev: Tree, b: Symbol, next: Tree): Tree
+      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree
+
+      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree
+      def flatMapGuard(cond: Tree, next: Tree): Tree
+
+      def fun(arg: Symbol, body: Tree): Tree
+      def ifThenElseZero(c: Tree, then: Tree): Tree
+      def _equals(checker: Tree, binder: Symbol): Tree
+      def _asInstanceOf(b: Symbol, tp: Type): Tree
+      def mkZero(tp: Type): Tree
+
+      def tupleSel(binder: Symbol)(i: Int): Tree
+      def index(tgt: Tree)(i: Int): Tree
+      def drop(tgt: Tree)(n: Int): Tree
+      def and(a: Tree, b: Tree): Tree
+      def _isInstanceOf(b: Symbol, tp: Type): Tree
+    }
+
+    def codegen: AbsCodegen
+
+    def typesConform(tp: Type, pt: Type) = ((tp eq pt) || (tp <:< pt))
+
+    abstract class CommonCodegen extends AbsCodegen { import CODE._
+      def fun(arg: Symbol, body: Tree): Tree           = Function(List(ValDef(arg)), body)
+      def genTypeApply(tfun: Tree, args: Type*): Tree  = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
+      def tupleSel(binder: Symbol)(i: Int): Tree       = (REF(binder) DOT nme.productAccessorName(i)) // make tree that accesses the i'th component of the tuple referenced by binder
+      def index(tgt: Tree)(i: Int): Tree               = tgt APPLY (LIT(i))
+      def drop(tgt: Tree)(n: Int): Tree                = (tgt DOT vpmName.drop) (LIT(n))
+      def _equals(checker: Tree, binder: Symbol): Tree = checker MEMBER_== REF(binder)          // NOTE: checker must be the target of the ==, that's the patmat semantics for ya
+      def and(a: Tree, b: Tree): Tree                  = a AND b
+      def ifThenElseZero(c: Tree, then: Tree): Tree     = IF (c) THEN then ELSE zero
+
+      // the force is needed mainly to deal with the GADT typing hack (we can't detect it otherwise as tp nor pt need contain an abstract type, we're just casting wildly)
+      def _asInstanceOf(t: Tree, tp: Type, force: Boolean = false): Tree      = { val tpX = repackExistential(tp)
+        if (!force && (t.tpe ne NoType) && t.isTyped && typesConform(t.tpe, tpX))  t //{ println("warning: emitted redundant asInstanceOf: "+(t, t.tpe, tp)); t } //.setType(tpX)
+        else gen.mkAsInstanceOf(t, tpX, true, false)
+      }
+
+      def _isInstanceOf(b: Symbol, tp: Type): Tree    = gen.mkIsInstanceOf(REF(b), repackExistential(tp), true, false)
+      // { val tpX = repackExistential(tp)
+      //   if (typesConform(b.info, tpX)) { println("warning: emitted spurious isInstanceOf: "+(b, tp)); TRUE }
+      //   else gen.mkIsInstanceOf(REF(b), tpX, true, false)
+      // }
+
+      def _asInstanceOf(b: Symbol, tp: Type): Tree    = { val tpX = repackExistential(tp)
+        if (typesConform(b.info, tpX)) REF(b) //{ println("warning: emitted redundant asInstanceOf: "+(b, b.info, tp)); REF(b) } //.setType(tpX)
+        else gen.mkAsInstanceOf(REF(b), tpX, true, false)
+      }
+
+      // duplicated out of frustration with cast generation
+      def mkZero(tp: Type): Tree = {
+        tp.typeSymbol match {
+          case UnitClass    => Literal(Constant())
+          case BooleanClass => Literal(Constant(false))
+          case FloatClass   => Literal(Constant(0.0f))
+          case DoubleClass  => Literal(Constant(0.0d))
+          case ByteClass    => Literal(Constant(0.toByte))
+          case ShortClass   => Literal(Constant(0.toShort))
+          case IntClass     => Literal(Constant(0))
+          case LongClass    => Literal(Constant(0L))
+          case CharClass    => Literal(Constant(0.toChar))
+          case _            => gen.mkAsInstanceOf(Literal(Constant(null)), tp, any = true, wrapInApply = false) // the magic incantation is true/false here
+        }
+      }
+    }
+  }
+
+  trait PureMatchMonadInterface extends MatchMonadInterface {
+    val matchStrategy: Tree
+
+    def inMatchMonad(tp: Type): Type = appliedType(oneSig, List(tp)).finalResultType
+    def pureType(tp: Type): Type     = appliedType(oneSig, List(tp)).paramTypes.head
+    protected def matchMonadSym      = oneSig.finalResultType.typeSymbol
+
+    import CODE._
+    def __match(n: Name): SelectStart = matchStrategy DOT n
+
+    private lazy val oneSig: Type =
+      typer.typed(__match(vpmName.one), EXPRmode | POLYmode | TAPPmode | FUNmode, WildcardType).tpe  // TODO: error message    
+  }
+
+  trait PureCodegen extends CodegenCore with PureMatchMonadInterface {
+    def codegen: AbsCodegen = pureCodegen
+
+    object pureCodegen extends CommonCodegen { import CODE._
+      //// methods in MatchingStrategy (the monad companion) -- used directly in translation
+      // __match.runOrElse(`scrut`)(`scrutSym` => `matcher`)
+      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): Tree
+        = __match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, matcher))
+      // __match.one(`res`)
+      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = (__match(vpmName.one)) (res)
+      // __match.zero
+      def zero: Tree = __match(vpmName.zero)
+      // __match.guard(`c`, `then`)
+      def guard(c: Tree, then: Tree, tp: Type): Tree = __match(vpmName.guard) APPLY (c, then)
+
+      //// methods in the monad instance -- used directly in translation
+      // `prev`.flatMap(`b` => `next`)
+      def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = (prev DOT vpmName.flatMap)(fun(b, next))
+      // `thisCase`.orElse(`elseCase`)
+      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = (thisCase DOT vpmName.orElse) APPLY (elseCase)
+      //  __match.guard(`cond`, `res`).flatMap(`nextBinder` => `next`)
+      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree = flatMap(guard(cond, res, nextBinderTp), nextBinder, next)
+      //  __match.guard(`guardTree`, ()).flatMap((_: P[Unit]) => `next`)
+      def flatMapGuard(guardTree: Tree, next: Tree): Tree = flatMapCond(guardTree, CODE.UNIT, freshSym(guardTree.pos, pureType(UnitClass.tpe)), pureType(UnitClass.tpe), next)
+    }
+  }
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// OPTIMIZATIONS
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // decisions, decisions
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
+  trait TreeMakerApproximation extends TreeMakers { self: CodegenCore =>
     object Test {
       var currId = 0
     }
@@ -957,25 +1233,16 @@ defined class Foo */
       override def toString = testedPath +" (<: && ==) "+ pt +"#"+ id
     }
 
-    /** a flow-sensitive, generalised, common sub-expression elimination
-     * reuse knowledge from performed tests
-     * the only sub-expressions we consider are the conditions and results of the three tests (type, type&equality, equality)
-     * when a sub-expression is share, it is stored in a mutable variable
-     * the variable is floated up so that its scope includes all of the program that shares it
-     * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree)
-     *
-     * intended to be generalised to exhaustivity/reachability checking
-     */
-    def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
+    def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = {
       // 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)
+      val pointsToBound            = collection.mutable.HashSet(root)
 
       // the substitution that renames variables to variables in pointsToBound
       var normalize: Substitution  = EmptySubstitution
 
       // replaces a variable (in pointsToBound) by a selection on another variable in pointsToBound
       // TODO check:
-      //   pointsToBound -- accumSubst.from == Set(prevBinder) && (accumSubst.from.toSet -- pointsToBound) isEmpty
+      //   pointsToBound -- accumSubst.from == Set(root) && (accumSubst.from.toSet -- pointsToBound) isEmpty
       var accumSubst: Substitution = EmptySubstitution
 
       val trees = new collection.mutable.HashSet[Tree]
@@ -1031,12 +1298,28 @@ defined class Foo */
              | GuardTreeMaker(_)
              | ProductExtractorTreeMaker(_, Some(_), _)             => Havoc
           case AlternativesTreeMaker(_, _, _)                       => Havoc // TODO: can do better here
-          case SubstOnlyTreeMaker(_)                                => Top
+          case SubstOnlyTreeMaker(_, _)                             => Top
           case BodyTreeMaker(_, _)                                  => Havoc
         }, tm)
       }
 
-      val testss = cases.map { _ map approximateTreeMaker }
+      cases.map { _ map approximateTreeMaker }
+    }
+  }
+
+////
+  trait CommonSubconditionElimination extends TreeMakerApproximation { self: OptimizedCodegen =>
+    /** a flow-sensitive, generalised, common sub-expression elimination
+     * reuse knowledge from performed tests
+     * the only sub-expressions we consider are the conditions and results of the three tests (type, type&equality, equality)
+     * when a sub-expression is share, it is stored in a mutable variable
+     * the variable is floated up so that its scope includes all of the program that shares it
+     * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree)
+     *
+     * intended to be generalised to exhaustivity/reachability checking
+     */
+    def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
+      val testss = approximateMatch(prevBinder, cases)
 
       // interpret:
       val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]]
@@ -1067,7 +1350,11 @@ 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 map { tests =>
+      val reused = new collection.mutable.HashMap[TreeMaker, ReusedCondTreeMaker]
+      var okToCall = false
+      val reusedOrOrig = (tm: TreeMaker) => {assert(okToCall); reused.getOrElse(tm, tm)}
+
+      val res = testss map { tests =>
         var currDeps = Set[Cond]()
         val (sharedPrefix, suffix) = tests span { test =>
           (test.cond eq Top) || (for(
@@ -1079,18 +1366,67 @@ defined class Foo */
         }
 
         val collapsedTreeMakers = if (sharedPrefix.nonEmpty) { // even sharing prefixes of length 1 brings some benefit (overhead-percentage for compiler: 26->24%, lib: 19->16%)
-          for (test <- sharedPrefix; reusedTest <- test.reuses; if reusedTest.treeMaker.isInstanceOf[FunTreeMaker])
-            reusedTest.treeMaker.asInstanceOf[FunTreeMaker].reused = true
+          for (test <- sharedPrefix; reusedTest <- test.reuses) reusedTest.treeMaker match {
+            case reusedCTM: CondTreeMaker => reused(reusedCTM) = ReusedCondTreeMaker(reusedCTM)
+            case _ =>
+          }
+
           // println("sharedPrefix: "+ sharedPrefix)
           for (lastShared <- sharedPrefix.reverse.dropWhile(_.cond eq Top).headOption;
                lastReused <- lastShared.reuses)
-            yield ReusingCondTreeMaker(sharedPrefix map (t => (t.treeMaker, t.reuses map (_.treeMaker)))) :: suffix.map(_.treeMaker)
+            yield ReusingCondTreeMaker(sharedPrefix, reusedOrOrig) :: 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)
       }
+      okToCall = true // TODO: remove (debugging)
+
+      res mapConserve (_ mapConserve reusedOrOrig)
+    }
+
+    object ReusedCondTreeMaker {
+      def apply(orig: CondTreeMaker) = new ReusedCondTreeMaker(orig.prevBinder, orig.nextBinder, orig.cond, orig.res, orig.pos)
+    }
+    class ReusedCondTreeMaker(prevBinder: Symbol, val nextBinder: Symbol, cond: Tree, res: Tree, pos: Position) extends TreeMaker { import CODE._
+      lazy val localSubstitution        = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
+      lazy val storedCond               = freshSym(pos, BooleanClass.tpe, "rc") setFlag MUTABLE
+      lazy val treesToHoist: List[Tree] = {
+        nextBinder setFlag MUTABLE
+        List(storedCond, nextBinder) map { b => VAL(b) === codegen.mkZero(b.info) }
+      }
+
+      // TODO: finer-grained duplication
+      def chainBefore(next: Tree, pt: Type): Tree = // assert(codegen eq optimizedCodegen)
+        atPos(pos)(optimizedCodegen.flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate))
+    }
+
+    case class ReusingCondTreeMaker(sharedPrefix: List[Test], toReused: TreeMaker => TreeMaker) extends TreeMaker { import CODE._
+      lazy val dropped_priors = sharedPrefix map (t => (toReused(t.treeMaker), t.reuses map (test => toReused(test.treeMaker))))
+      lazy val localSubstitution = {
+        val (from, to) = dropped_priors.collect {
+          case (dropped: CondTreeMaker, Some(prior: ReusedCondTreeMaker)) =>
+            (dropped.nextBinder, REF(prior.nextBinder))
+          }.unzip
+        val oldSubs = dropped_priors.collect {
+          case (dropped: TreeMaker, _) =>
+            dropped.substitution
+          }
+        oldSubs.foldLeft(Substitution(from, to))(_ >> _)
+      }
+
+      def chainBefore(next: Tree, pt: Type): Tree = {
+        val cond = REF(dropped_priors.reverse.collectFirst{case (_, Some(ctm: ReusedCondTreeMaker)) => ctm}.get.storedCond)
+
+        IF (cond) THEN BLOCK(
+          substitution(next).duplicate // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift, and its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S)
+        ) ELSE codegen.zero
+      }
     }
+  }
+
 
+  //// DCE
+  trait DeadCodeElimination extends TreeMakers { self: CodegenCore =>
     // TODO: non-trivial dead-code elimination
     // e.g., the following match should compile to a simple instanceof:
     //   case class Ident(name: String)
@@ -1099,21 +1435,10 @@ defined class Foo */
       // do minimal DCE
       cases
     }
+  }
 
-
-    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
-      }
-      removeSubstOnly(treeMakers)
-    }
-
+  //// SWITCHES
+  trait SwitchEmission extends TreeMakers with OptimizedMatchMonadInterface { self: CodegenCore =>
     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
@@ -1130,7 +1455,7 @@ defined class Foo */
 
     private val switchableTpes = Set(ByteClass.tpe, ShortClass.tpe, IntClass.tpe, CharClass.tpe)
 
-    def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = if (!optimizingCodeGen) None else {
+    override def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = {
       def sequence[T](xs: List[Option[T]]): Option[List[T]] =
         if (xs exists (_.isEmpty)) None else Some(xs.flatten)
 
@@ -1171,7 +1496,7 @@ defined class Foo */
       }
 
       if (!isSwitchableTpe(scrut.tpe))
-        None
+        None // TODO: emit a cast of the scrutinee and a switch on the cast scrutinee if patterns allow switch but the type of the scrutinee doesn't
       else {
         sequence(caseDefs) map { caseDefs =>
           import CODE._
@@ -1201,188 +1526,27 @@ defined class Foo */
         }
       }
     }
-
-    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, hasDefault) =
-          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
-
-            // do this check on casesUnOpt, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one
-            // exhaustivity and reachability must be checked before optimization as well
-            val hasDefault = casesUnOpt.nonEmpty && {
-              val nonTrivLast = casesUnOpt.last
-              nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
-            }
-
-            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), hasDefault)
-          } else (pmgen.zero, false)
-
-        val expr = pmgen.runOrElse(scrut, matcher, scrutSym.info, if (isFullyDefined(pt)) pt else NoType, hasDefault)
-        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], 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.newAnonymousFunctionValue(t.pos)
-            // 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)
-              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
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-    object Substitution {
-      def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
-      // requires sameLength(from, to)
-      def apply(from: List[Symbol], to: List[Tree]) =
-        if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
-    }
-
-    class Substitution(val from: List[Symbol], val to: List[Tree]) {
-      def apply(tree: Tree): Tree = typedSubst(tree, from, to)
-
-      // the substitution that chains `other` before `this` substitution
-      // forall t: Tree. this(other(t)) == (this >> other)(t)
-      def >>(other: Substitution): Substitution = {
-        val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) =>  !other.from.contains(f) }
-        new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
-      }
-      override def toString = (from zip to) mkString("Substitution(", ", ", ")")
-    }
-
-    object EmptySubstitution extends Substitution(Nil, Nil) {
-      override def apply(tree: Tree): Tree = tree
-      override def >>(other: Substitution): Substitution = other
-    }
-
-
-    def matchingMonadType: Type
-    def typedSubst(tree: Tree, from: List[Symbol], to: List[Tree]): Tree
-    def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol
-    def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree
-    def typeTest(binder: Symbol, pt: Type): Tree
-
-    // codegen relevant to the structure of the translation (how extractors are combined)
-    trait AbsCodeGen { import CODE.UNIT
-      def runOrElse(scrut: Tree, matcher: Tree, scrutTp: Type, resTp: Type, hasDefault: Boolean): Tree
-      def flatMap(a: Tree, b: Tree): Tree
-      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree
-      def flatMapGuard(cond: Tree, next: Tree): Tree
-      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
-      def mkZero(tp: Type): Tree
-    }
-
-    def pmgen: AbsCodeGen
-    def typed(tree: Tree, mode: Int, pt: Type): Tree // implemented in MatchTranslator
   }
 
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-// generate actual trees
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-  trait MatchCodeGen extends TreeMakers {
-    lazy val pmgen: CommonCodeGen with MatchingStrategyGen with MonadInstGen =
-      if (optimizingCodeGen) (new CommonCodeGen with OptimizedCodeGen {})
-      else (new CommonCodeGen with MatchingStrategyGen with MonadInstGen {})
-
-    import CODE._
-
-    trait MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
-      // methods in MatchingStrategy (the monad companion) -- used directly in translation
-      def runOrElse(scrut: Tree, matcher: Tree, scrutTp: Type, resTp: Type, hasDefault: Boolean): Tree = genTypeApply(matchingStrategy DOT vpmName.runOrElse, scrutTp, resTp) APPLY (scrut) APPLY (matcher)  // matchingStrategy.runOrElse(scrut)(matcher)
-      // *only* used to wrap the RHS of a body (isDefinedAt synthesis relies on this)
-      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree                       = (matchingStrategy DOT vpmName.one) (_asInstanceOf(res, bodyPt, force = true)) // matchingStrategy.one(res), like one, but blow this one away for isDefinedAt (since it's the RHS of a case)
-      def zero: Tree                                                              = matchingStrategy DOT vpmName.zero                                // matchingStrategy.zero
-      def guard(c: Tree, then: Tree, tp: Type): Tree                              = genTypeApply((matchingStrategy DOT vpmName.guard), repackExistential(tp)) APPLY (c, then) // matchingStrategy.guard[tp](c, then)
-    }
+  trait OptimizedMatchMonadInterface extends MatchMonadInterface {
+    override def inMatchMonad(tp: Type): Type = optionType(tp)
+    override def pureType(tp: Type): Type     = tp
+    override protected def matchMonadSym      = OptionClass
+  }
 
-    trait MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
-      // methods in the monad instance -- used directly in translation
-      def flatMap(a: Tree, b: Tree): Tree                             = (a DOT vpmName.flatMap)(b)
-      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = (genTypeApply(thisCase DOT vpmName.orElse, pt)) APPLY (elseCase)
+  trait OptimizedCodegen extends CodegenCore with TypedSubstitution with OptimizedMatchMonadInterface {
+    override def codegen: AbsCodegen = optimizedCodegen
 
-      // TODO: the trees generated by flatMapCond and flatMapGuard may need to be distinguishable by exhaustivity checking -- they aren't right now
-      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol,
-                      nextBinderTp: Type, next: Tree): Tree           = flatMap(guard(cond, res, nextBinderTp), fun(nextBinder, next))
-      def flatMapGuard(guardTree: Tree, next: Tree): Tree             = flatMapCond(guardTree, CODE.UNIT, freshSym(guardTree.pos, UnitClass.tpe), UnitClass.tpe, next)
-    }
+    // trait AbsOptimizedCodegen extends AbsCodegen {
+    //   def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree
+    // }
+    // def optimizedCodegen: AbsOptimizedCodegen
 
     // when we know we're targetting Option, do some inlining the optimizer won't do
-    // `o.flatMap(f)` becomes `if(o == None) None else f(o.get)`, similarly for orElse and guard
-    // this is a special instance of the advanced inlining optimization that takes a method call on
-    // an object of a type that only has two concrete subclasses, and inlines both bodies, guarded by an if to distinguish the two cases
-    // this trait overrides ALL of the methods of MatchingStrategyGen with MonadInstGen
-    trait OptimizedCodeGen extends CommonCodeGen with MatchingStrategyGen with MonadInstGen {
+    // for example, `o.flatMap(f)` becomes `if(o == None) None else f(o.get)`, similarly for orElse and guard
+    //   this is a special instance of the advanced inlining optimization that takes a method call on
+    //   an object of a type that only has two concrete subclasses, and inlines both bodies, guarded by an if to distinguish the two cases
+    object optimizedCodegen extends CommonCodegen /*with AbsOptimizedCodegen*/ { import CODE._
       lazy val zeroSym        = freshSym(NoPosition, optionType(NothingClass.tpe), "zero")
 
       /** Inline runOrElse and get rid of Option allocations
@@ -1394,23 +1558,22 @@ defined class Foo */
       @inline private def dontStore(tp: Type) = (tp.typeSymbol eq UnitClass) || (tp.typeSymbol eq NothingClass)
       lazy val keepGoing = freshSym(NoPosition, BooleanClass.tpe, "keepGoing") setFlag MUTABLE
       lazy val matchRes  = freshSym(NoPosition, AnyClass.tpe, "matchRes") setFlag MUTABLE
-      override def runOrElse(scrut: Tree, matcher: Tree, scrutTp: Type, resTp: Type, hasDefault: Boolean) = {
-        val Function(List(x: ValDef), body) = matcher
+      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean) = {
         matchRes.info = if (resTp ne NoType) resTp.widen else AnyClass.tpe // we don't always know resTp, and it might be AnyVal, in which case we can't assign NULL
         if (dontStore(resTp)) matchRes resetFlag MUTABLE  // don't assign to Unit-typed var's, in fact, make it a val -- conveniently also works around SI-5245
         BLOCK(
-          VAL(zeroSym)   === REF(NoneModule), // TODO: can we just get rid of explicitly emitted zero? don't know how to do that as a local rewrite...
-          VAL(x.symbol)  === scrut, // reuse the symbol of the function's argument to avoid creating a fresh one and substituting it for x.symbol in body -- the owner structure is repaired by fixerUpper
+          VAL(zeroSym)   === REF(NoneModule),       // TODO: can we just get rid of explicitly emitted zero? don't know how to do that as a local rewrite...
+          VAL(scrutSym)  === scrut,                 // reuse the symbol of the function's argument to avoid creating a fresh one and substituting it for scrutSym in `matcher` -- the owner structure is repaired by fixerUpper
           VAL(matchRes)  === mkZero(matchRes.info), // must cast to deal with GADT typing, hence the private mkZero above
           VAL(keepGoing) === TRUE,
-          body,
+          matcher,
           if(hasDefault) REF(matchRes)
-          else (IF (REF(keepGoing)) THEN MATCHERROR(REF(x.symbol)) ELSE REF(matchRes))
+          else (IF (REF(keepGoing)) THEN MATCHERROR(REF(scrutSym)) ELSE REF(matchRes))
         )
       }
 
       // only used to wrap the RHS of a body
-      override def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = {
+      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = {
         BLOCK(
           if (dontStore(matchPt)) res // runOrElse hasn't been called yet, so matchRes.isMutable is irrelevant, also, tp may be a subtype of resTp used in runOrElse...
           else (REF(matchRes) === res), // _asInstanceOf(res, tp.widen, force = true)
@@ -1419,194 +1582,57 @@ defined class Foo */
         )
       }
 
-      override def zero: Tree = REF(zeroSym)
+      def zero: Tree = REF(zeroSym)
 
-      // guard is only used by flatMapCond and flatMapGuard, which are overridden
-      override def guard(c: Tree, then: Tree, tp: Type): Tree = throw new NotImplementedError("guard is never called by optimizing codegen")
+      def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = {
+        val tp      = inMatchMonad(b.tpe)
+        val prevSym = freshSym(prev.pos, tp, "o")
+        val isEmpty = tp member vpmName.isEmpty
+        val get     = tp member vpmName.get
 
-      override def flatMap(opt: Tree, fun: Tree): Tree = fun match {
-        case Function(List(x: ValDef), body) =>
-          val tp      = inMatchMonad(x.symbol.tpe)
-          val vs      = freshSym(opt.pos, tp, "o")
-          val isEmpty = tp member vpmName.isEmpty
-          val get     = tp member vpmName.get
-          val v       = VAL(vs) === opt
-
-          BLOCK(
-            v,
-            IF (vs DOT isEmpty) THEN zero ELSE typedSubst(body, List(x.symbol), List(vs DOT get)) // must be isEmpty and get as we don't control the target of the call (could be the result of a user-defined extractor)
-          )
-        case _ => println("huh?")
-          (opt DOT vpmName.flatMap)(fun)
+        BLOCK(
+          VAL(prevSym) === prev,
+          IF (prevSym DOT isEmpty) THEN zero ELSE Substitution(b, prevSym DOT get)(next) // must be isEmpty and get as we don't control the target of the call (could be the result of a user-defined extractor)
+        )
       }
 
-      override def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = {
+      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = {
         BLOCK(
           thisCase,
           IF (REF(keepGoing)) THEN elseCase ELSE zero // leave trailing zero for now, otherwise typer adds () anyway
         )
       }
 
-      override def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree =
+      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree =
         IF (cond) THEN BLOCK(
           VAL(nextBinder) === res,
           next
         ) ELSE zero
 
-      override def flatMapGuard(guardTree: Tree, next: Tree): Tree =
-        IF (guardTree) THEN next ELSE zero
-    }
-
-    @inline private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
-      if (origTp == null || origTp == NoType) to
-      // important: only type when actually substing and when original tree was typed
-      // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
-      else typed(to, EXPRmode, WildcardType)
-
-    // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
-    // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
-    def typedSubst(tree: Tree, from: List[Symbol], to: List[Tree]): Tree = {
-      // according to -Ystatistics 10% of translateMatch's time is spent in this method...
-      // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
-      if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
-      else (new Transformer {
-        override def transform(tree: Tree): Tree = {
-          def subst(from: List[Symbol], to: List[Tree]): Tree =
-            if (from.isEmpty) tree
-            else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate, tree.tpe)
-            else subst(from.tail, to.tail)
-
-          tree match {
-            case Ident(_) => subst(from, to)
-            case _        => super.transform(tree)
-          }
-        }
-      }).transform(tree)
-    }
-
-    var ctr = 0
-    def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x") = {ctr += 1;
-      // assert(owner ne null)
-      // assert(owner ne NoSymbol)
-      NoSymbol.newTermSymbol(vpmName.counted(prefix, ctr), pos) setInfo repackExistential(tp)
-    }
-
-    def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match {
-      case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args)
-      case _ => tp
-    }
+      def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree =
+        IF (cond) THEN BLOCK(
+          condSym    === TRUE,
+          nextBinder === res,
+          next
+        ) ELSE zero
 
-    object vpmName {
-      val one       = newTermName("one")
-      val drop      = newTermName("drop")
-      val flatMap   = newTermName("flatMap")
-      val get       = newTermName("get")
-      val guard     = newTermName("guard")
-      val isEmpty   = newTermName("isEmpty")
-      val orElse    = newTermName("orElse")
-      val outer     = newTermName("<outer>")
-      val runOrElse = newTermName("runOrElse")
-      val zero      = newTermName("zero")
-
-      def counted(str: String, i: Int) = newTermName(str+i)
+      def flatMapGuard(guardTree: Tree, next: Tree): Tree =
+        IF (guardTree) THEN next ELSE zero
     }
+  }
 
 
-    def typesConform(tp: Type, pt: Type) = ((tp eq pt) || (tp <:< pt))
-
-    trait CommonCodeGen extends AbsCodeGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
-      def fun(arg: Symbol, body: Tree): Tree           = Function(List(ValDef(arg)), body)
-      def genTypeApply(tfun: Tree, args: Type*): Tree  = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
-      def tupleSel(binder: Symbol)(i: Int): Tree       = (REF(binder) DOT nme.productAccessorName(i)) // make tree that accesses the i'th component of the tuple referenced by binder
-      def index(tgt: Tree)(i: Int): Tree               = tgt APPLY (LIT(i))
-      def drop(tgt: Tree)(n: Int): Tree                = (tgt DOT vpmName.drop) (LIT(n))
-      def _equals(checker: Tree, binder: Symbol): Tree = checker MEMBER_== REF(binder)          // NOTE: checker must be the target of the ==, that's the patmat semantics for ya
-      def and(a: Tree, b: Tree): Tree                  = a AND b
-      def condOptimized(c: Tree, then: Tree): Tree     = IF (c) THEN then ELSE zero
-
-      // the force is needed mainly to deal with the GADT typing hack (we can't detect it otherwise as tp nor pt need contain an abstract type, we're just casting wildly)
-      def _asInstanceOf(t: Tree, tp: Type, force: Boolean = false): Tree      = { val tpX = repackExistential(tp)
-        if (!force && (t.tpe ne NoType) && t.isTyped && typesConform(t.tpe, tpX))  t //{ println("warning: emitted redundant asInstanceOf: "+(t, t.tpe, tp)); t } //.setType(tpX)
-        else gen.mkAsInstanceOf(t, tpX, true, false)
-      }
-
-      def _isInstanceOf(b: Symbol, tp: Type): Tree    = gen.mkIsInstanceOf(REF(b), repackExistential(tp), true, false)
-      // { val tpX = repackExistential(tp)
-      //   if (typesConform(b.info, tpX)) { println("warning: emitted spurious isInstanceOf: "+(b, tp)); TRUE }
-      //   else gen.mkIsInstanceOf(REF(b), tpX, true, false)
-      // }
-
-      def _asInstanceOf(b: Symbol, tp: Type): Tree    = { val tpX = repackExistential(tp)
-        if (typesConform(b.info, tpX)) REF(b) //{ println("warning: emitted redundant asInstanceOf: "+(b, b.info, tp)); REF(b) } //.setType(tpX)
-        else gen.mkAsInstanceOf(REF(b), tpX, true, false)
-      }
-
-      // duplicated out of frustration with cast generation
-      def mkZero(tp: Type): Tree = {
-        tp.typeSymbol match {
-          case UnitClass    => Literal(Constant())
-          case BooleanClass => Literal(Constant(false))
-          case FloatClass   => Literal(Constant(0.0f))
-          case DoubleClass  => Literal(Constant(0.0d))
-          case ByteClass    => Literal(Constant(0.toByte))
-          case ShortClass   => Literal(Constant(0.toShort))
-          case IntClass     => Literal(Constant(0))
-          case LongClass    => Literal(Constant(0L))
-          case CharClass    => Literal(Constant(0.toChar))
-          case _            => gen.mkAsInstanceOf(Literal(Constant(null)), tp, any = true, wrapInApply = false) // the magic incantation is true/false here
-        }
-      }
+  trait MatchOptimizations extends CommonSubconditionElimination
+                              with DeadCodeElimination
+                              with SwitchEmission
+                              with OptimizedCodegen { self: TreeMakers =>
+    override def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) = {
+      val optCases = doCSE(prevBinder, doDCE(prevBinder, cases, pt), pt)
+      val toHoist = (
+        for (treeMakers <- optCases)
+          yield treeMakers.collect{case tm: ReusedCondTreeMaker => tm.treesToHoist}
+        ).flatten.flatten.toList
+      (optCases, toHoist)
     }
-
-    def matchingStrategy: Tree
   }
 }
-
-// object noShadowedUntyped extends Traverser {
-//   override def traverse(t: Tree) {
-//     if ((t.tpe ne null) && (t.tpe ne NoType)) okTree = t
-//     else if(okTree ne null) println("untyped subtree "+ t +" in typed tree"+ okTree +" : "+ okTree.tpe)
-//     super.traverse(t)
-//   }
-//   var okTree: Tree = null
-// }
-// private def c(t: Tree): Tree = noShadowedUntyped(t)
-
-    //   def approximateTreeMaker(tm: TreeMaker): List[Test] = tm match {
-    //     case ExtractorTreeMaker(extractor, _, _) => HavocTest
-    //     case FilteredExtractorTreeMaker(extractor, lenGuard, _, _) => HavocTest
-    //     case ProductExtractorTreeMaker(testedBinder, lenGuard, _) => TopTest // TODO: (testedBinder ne null) and lenGuard
-    //
-    //     // cond = typeTest(prevBinder, nextBinderTp)
-    //     // res  = pmgen._asInstanceOf(prevBinder, nextBinderTp)
-    //     case TypeTestTreeMaker(testedBinder, pt, _) =>
-    //
-    //     // cond = typeAndEqualityTest(patBinder, pt)
-    //     // res  = pmgen._asInstanceOf(patBinder, nextBinderTp)
-    //     case TypeAndEqualityTestTreeMaker(_, testedBinder, pt, _) =>
-    //
-    //     // cond = pmgen._equals(patTree, prevBinder)
-    //     // res  = CODE.REF(prevBinder)
-    //     case EqualityTestTreeMaker(testedBinder, rhs, _) =>
-    //
-    //     case AlternativesTreeMaker(_, alts: *) =>
-    //
-    //     case GuardTreeMaker(guardTree) =>
-    //   }
-
-    // // TODO: it's not exactly sound to represent an unapply-call by its symbol... also need to consider the prefix, like the outer-test (can this be captured as the path to this test?)
-    // type ExtractorRepr = Symbol
-    //
-    // // TODO: we're undoing tree-construction that we ourselves performed earlier -- how about not-doing so we don't have to undo?
-    // private def findBinderArgOfApply(extractor: Tree, unappSym: Symbol): Symbol = {
-    //   class CollectTreeTraverser[T](pf: PartialFunction[Tree => T]) extends Traverser {
-    //     val hits = new ListBuffer[T]
-    //     override def traverse(t: Tree) {
-    //       if (pf.isDefinedAt(t)) hits += pf(t)
-    //       super.traverse(t)
-    //     }
-    //   }
-    //   val trav = new CollectTreeTraverser{ case Apply(unapp, List(arg)) if unapp.symbol eq unappSym => arg.symbol}
-    //   trav.traverse(extractor)
-    //   trav.hits.headOption getOrElse NoSymbol
-    // }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 2749f99e18..d039515320 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -3303,7 +3303,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
             val owntype = elimAnonymousClass(owntype0)
             if (needAdapt) cases1 = cases1 map (adaptCase(_, owntype))
 
-            (new MatchTranslator(this)).translateMatch(selector1, cases1, owntype) match {
+            (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)
diff --git a/src/library/scala/MatchingStrategy.scala b/src/library/scala/MatchingStrategy.scala
deleted file mode 100644
index d11598bad6..0000000000
--- a/src/library/scala/MatchingStrategy.scala
+++ /dev/null
@@ -1,27 +0,0 @@
-package scala
-
-abstract class MatchingStrategy[M[+x]] {
-  // runs the matcher on the given input
-  def runOrElse[T, U](in: T)(matcher: T => M[U]): U
-
-  def zero: M[Nothing]
-  def one[T](x: T): M[T]
-  def guard[T](cond: Boolean, then: => T): M[T]
-  def isSuccess[T, U](x: T)(f: T => M[U]): Boolean // used for isDefinedAt
-
-  def caseResult[T](x: T): M[T] = one(x) // used as a marker to distinguish the RHS of a case (case pat => RHS) and intermediate successes
-  // when deriving a partial function from a pattern match, 
-  // we need to distinguish the RHS of a case, which should not be evaluated when computing isDefinedAt,
-  // from an intermediate result (which must be computed)
-}
-
-object MatchingStrategy {
-  implicit object OptionMatchingStrategy extends MatchingStrategy[Option] {
-    type M[+x] = Option[x]
-    @inline def runOrElse[T, U](x: T)(f: T => M[U]): U = f(x) getOrElse (throw new MatchError(x))
-    @inline def zero: M[Nothing] = None
-    @inline def one[T](x: T): M[T] = Some(x)
-    @inline def guard[T](cond: Boolean, then: => T): M[T] = if(cond) Some(then) else None
-    @inline def isSuccess[T, U](x: T)(f: T => M[U]): Boolean = !f(x).isEmpty
-  }
-}
\ No newline at end of file