TreeMaker approximation refactorings and bug fixes

- TypeTestTreeMaker subsumes the old TypeTestTM and TypeAndEqualityTM
  its type- and equality-testing logic is configurable so that it can:
    - generate trees (main purpose)
    - check whether this tree maker is a pure type test
    - generate the proposition that models this tree maker
      (for exhaustivity and other analyses)

- [CSE] subst binders of dropped tm's to stored ones
  somehow the refactoring broke the replacement of the binder of dropped
  treemakers by the binder of the reused treemaker

  when replacing

  TM1(x1 => ...) >> TM2(x2 => ...) >> TM3(x3 => ...) >>  ...
  TM1'(x1' => ...) >> TM2'(x2' => ...) >> TM3(x3' => ...) >> ...

  by

  Memo1(x1 => ...) >> TM2(x2 => ...) >> Memo2(x3 => ...) >>  ...
  Reuse(Memo2)...

  you need to replace x1' and x2' by x1

  since TM2 tested a shared condition but was not memo-ised,
  that implies it simply passed x1 through to x3 unmodified,
  and x2' can simply use the stored x1

- type of first uniqued binder sets type of tree
  when approximating a tree of treemakers as a DAG,
  where sharing indicates the same value is tested,
  use the type of the binder that was first used to
  create a unique tree as the type of that tree,
  and thus all trees used for the same binder in the future

- track substitution of alternatives when approximating

- error on unswitchable @switch annotated matches
  if we can't turn a match (with more than two cases) into a switch,
  but the user insists, emit an error

misc notes:
- when all you need is nextBinder, FunTreeMaker is your guy
- must pass flag to TypeTestTM for extractorarg test
  case TypeTestTreeMaker(prevBinder, testedBinder, expectedTp, nextBinderTp)
  (prevBinder eq testedBinder) does not imply it's a pure type test for an extractor call
  note that the expected type for an extractor argument is not a type pattern,
  thus we only do a classic type test -- the idea was to detect that case by noticing we're
  being called with the same previous and tested binder, but that case also arises
  for Typed patterns

1 files changed, 401 insertions, 225 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
index 61e02edaff..d12b8f848f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
@@ -12,6 +12,8 @@ import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC}
 import language.postfixOps
 import scala.tools.nsc.transform.TypingTransformers
 import scala.tools.nsc.transform.Transform
+import scala.collection.mutable.HashSet
+import scala.collection.mutable.HashMap
 
 /** Translate pattern matching.
   *
@@ -306,7 +308,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
             // it tests the type, checks the outer pointer and casts to the expected type
             // TODO: the outer check is mandated by the spec for case classes, but we do it for user-defined unapplies as well [SPEC]
             // (the prefix of the argument passed to the unapply must equal the prefix of the type of the binder)
-            val treeMaker = TypeTestTreeMaker(patBinder, extractor.paramType, pos)
+            val treeMaker = TypeTestTreeMaker(patBinder, patBinder, extractor.paramType, extractor.paramType)(pos, extractorArgTypeTest = true)
             (List(treeMaker), treeMaker.nextBinder)
           } else (Nil, patBinder)
 
@@ -364,7 +366,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         // must treat Typed and Bind together -- we need to know the patBinder of the Bind pattern to get at the actual type
         case MaybeBoundTyped(subPatBinder, pt) =>
           // a typed pattern never has any subtrees
-          noFurtherSubPats(TypeAndEqualityTestTreeMaker(subPatBinder, patBinder, pt, pos))
+          noFurtherSubPats(TypeTestTreeMaker(subPatBinder, patBinder, pt, glb(List(patBinder.info.widen, pt)).normalize)(pos))
 
         /** A pattern binder x@p consists of a pattern variable x and a pattern p.
             The type of the variable x is the static type T of the pattern p.
@@ -562,8 +564,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 
       protected def lengthGuard(binder: Symbol): Option[Tree] =
         // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied
-        if (!isSeq || (expectedLength < minLenToCheck)) None
-        else { import CODE._
+        checkedLength map { expectedLength => import CODE._
           // `binder.lengthCompare(expectedLength)`
           def checkExpectedLength = (seqTree(binder) DOT seqLenCmp)(LIT(expectedLength))
 
@@ -575,8 +576,14 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
             else             _ INT_== _
 
           // `if (binder != null && $checkExpectedLength [== | >=] 0) then else zero`
-          Some((seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO))
+          (seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO)
         }
+
+      def checkedLength: Option[Int] =
+        // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied
+        if (!isSeq || (expectedLength < minLenToCheck)) None
+        else Some(expectedLength)
+
     }
 
     // TODO: to be called when there's a def unapplyProd(x: T): U
@@ -650,7 +657,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         // 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, 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)
+        ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder, Substitution(subPatBinders, subPatRefs(binder)))(resultType.typeSymbol == BooleanClass, checkedLength, patBinderOrCasted)
       }
 
       override protected def seqTree(binder: Symbol): Tree =
@@ -762,7 +769,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         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(", ", ", ")")
+      override def toString = (from.map(_.name) zip to) mkString("Substitution(", ", ", ")")
     }
 
     object EmptySubstitution extends Substitution(Nil, Nil) {
@@ -775,7 +782,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 // 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]) =
+    def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type, unchecked: Boolean): (List[List[TreeMaker]], List[Tree]) =
       (cases, Nil)
 
     def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type, matchFailGenOverride: Option[Tree => Tree]): Option[Tree] =
@@ -819,11 +826,13 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
     case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker with NoNewBinders {
       def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(next eq EmptyTree)
         atPos(body.pos)(casegen.one(substitution(body))) // since SubstOnly treemakers are dropped, need to do it here
+      override def toString = "B"+(body, matchPt)
     }
 
     case class SubstOnlyTreeMaker(prevBinder: Symbol, nextBinder: Symbol) extends TreeMaker {
       val localSubstitution = Substitution(prevBinder, CODE.REF(nextBinder))
       def chainBefore(next: Tree)(casegen: Casegen): Tree = substitution(next)
+      override def toString = "S"+ localSubstitution
     }
 
     abstract class FunTreeMaker extends TreeMaker {
@@ -851,7 +860,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
      * the function's body is determined by the next TreeMaker
      * 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 {
+    case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol, localSubstitution: Substitution)(extractorReturnsBoolean: Boolean, val checkedLength: Option[Int], val prevBinder: Symbol) extends FunTreeMaker {
       def chainBefore(next: Tree)(casegen: Casegen): Tree = {
         val condAndNext = extraCond map (casegen.ifThenElseZero(_, next)) getOrElse next
         atPos(extractor.pos)(
@@ -860,136 +869,157 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         )
       }
 
-      override def toString = "X"+(extractor, nextBinder)
+      override def toString = "X"+(extractor, nextBinder.name)
     }
 
     // TODO: allow user-defined unapplyProduct
-    case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends TreeMaker { import CODE._
+    case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends FunTreeMaker { import CODE._
+      val nextBinder = prevBinder // just passing through
       def chainBefore(next: Tree)(casegen: Casegen): Tree = {
         val nullCheck = REF(prevBinder) OBJ_NE NULL
         val cond = extraCond map (nullCheck AND _) getOrElse nullCheck
         casegen.ifThenElseZero(cond, substitution(next))
       }
 
-      override def toString = "P"+(prevBinder,  extraCond getOrElse "", localSubstitution)
+      override def toString = "P"+(prevBinder.name,  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)
-        }
+    // typetag-based tests are inserted by the type checker
+    def needsTypeTest(tp: Type, pt: Type): Boolean = !(tp <:< pt)
+
+    object TypeTestTreeMaker {
+      // factored out so that we can consistently generate other representations of the tree that implements the test
+      // (e.g. propositions for exhaustivity and friends, boolean for isPureTypeTest)
+      trait TypeTestCondStrategy {
+        type Result
+
+        def outerTest(testedBinder: Symbol, expectedTp: Type): Result
+        // TODO: can probably always widen
+        def typeTest(testedBinder: Symbol, expectedTp: Type): Result
+        def nonNullTest(testedBinder: Symbol): Result
+        def equalsTest(pat: Tree, testedBinder: Symbol): Result
+        def eqTest(pat: Tree, testedBinder: Symbol): Result
+        def and(a: Result, b: Result): Result
+      }
+
+      object treeCondStrategy extends TypeTestCondStrategy { import CODE._
+        type Result = Tree
+
+        def and(a: Result, b: Result): Result                = a AND b
+        def typeTest(testedBinder: Symbol, expectedTp: Type) = codegen._isInstanceOf(testedBinder, expectedTp)
+        def nonNullTest(testedBinder: Symbol)                = REF(testedBinder) OBJ_NE NULL
+        def equalsTest(pat: Tree, testedBinder: Symbol)      = codegen._equals(pat, testedBinder)
+        def eqTest(pat: Tree, testedBinder: Symbol)          = REF(testedBinder) OBJ_EQ pat
 
-        // 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
+        def outerTest(testedBinder: Symbol, expectedTp: Type): Tree = {
+          val expectedOuter = 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
 
-        // first check cond, since that should ensure we're not selecting outer on null
-        codegen.and(cond, outerCheck)
+          (Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter
+        }
       }
-      else
-        cond
-    }
 
-    // containsUnchecked: also need to test when erasing pt loses crucial information (maybe we can recover it using a TypeTag)
-    def needsTypeTest(tp: Type, pt: Type): Boolean = !(tp <:< pt) // || containsUnchecked(pt)
-    // TODO: try to find the TypeTag for the binder's type and the expected type, and if they exists,
-    // check that the TypeTag of the binder's type conforms to the TypeTag of the expected type
-    private def typeTest(binderToTest: Symbol, expectedTp: Type, disableOuterCheck: Boolean = false, dynamic: Boolean = false): Tree = { import CODE._
-      // def coreTest =
-      if (disableOuterCheck) codegen._isInstanceOf(binderToTest, expectedTp) else maybeWithOuterCheck(binderToTest, expectedTp)(codegen._isInstanceOf(binderToTest, expectedTp))
-      // [Eugene to Adriaan] use `resolveErasureTag` instead of `findManifest`. please, provide a meaningful position
-      // if (opt.experimental && containsUnchecked(expectedTp)) {
-      //   if (dynamic) {
-      //     val expectedTpTagTree = findManifest(expectedTp, true)
-      //     if (!expectedTpTagTree.isEmpty)
-      //       ((expectedTpTagTree DOT "erasure".toTermName) DOT "isAssignableFrom".toTermName)(REF(binderToTest) DOT nme.getClass_)
-      //     else
-      //       coreTest
-      //   } else {
-      //     val expectedTpTagTree = findManifest(expectedTp, true)
-      //     val binderTpTagTree   = findManifest(binderToTest.info, true)
-      //     if(!(expectedTpTagTree.isEmpty || binderTpTagTree.isEmpty))
-      //       coreTest AND (binderTpTagTree DOT nme.CONFORMS)(expectedTpTagTree)
-      //     else
-      //       coreTest
-      //   }
-      // } else coreTest
-    }
+      object pureTypeTestChecker extends TypeTestCondStrategy {
+        type Result = Boolean
+
+        def typeTest(testedBinder: Symbol, expectedTp: Type): Result  = true
 
-    // 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, dynamic = true)
-      val res  = codegen._asInstanceOf(prevBinder, nextBinderTp)
-      override def toString = "TT"+(prevBinder, nextBinderTp)
+        def outerTest(testedBinder: Symbol, expectedTp: Type): Result = false
+        def nonNullTest(testedBinder: Symbol): Result                 = false
+        def equalsTest(pat: Tree, testedBinder: Symbol): Result       = false
+        def eqTest(pat: Tree, testedBinder: Symbol): Result           = false
+        def and(a: Result, b: Result): Result                         = false // we don't and type tests, so the conjunction must include at least one false
+      }
     }
 
-    // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations)
-    // TODO: normalize construction, which yields a combination of a EqualityTestTreeMaker (when necessary) and a TypeTestTreeMaker
-    case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends CondTreeMaker {
-      val nextBinderTp = glb(List(patBinder.info.widen, pt)).normalize
-
-      /** 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 typeTest(patBinder, pt.widen, disableOuterCheck = true)
-
-        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 TypeTags to improve tests (for erased types we can do better when we have a TypeTag)
-        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)
-          }
+    /** implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations)
+     *
+     * 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.
+    **/
+    case class TypeTestTreeMaker(prevBinder: Symbol, testedBinder: Symbol, expectedTp: Type, nextBinderTp: Type)(_pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker {
+      val pos = _pos
+
+      import TypeTestTreeMaker._
+      // println("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp))
+
+      lazy val outerTestNeeded = (
+          !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
+        && needsOuterTest(expectedTp, testedBinder.info, matchOwner))
+
+      // the logic to generate the run-time test that follows from the fact that
+      // a `prevBinder` is expected to have type `expectedTp`
+      // the actual tree-generation logic is factored out, since the analyses generate Cond(ition)s rather than Trees
+      // 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 renderCondition(cs: TypeTestCondStrategy): cs.Result = {
+        import cs._
+
+        def default =
+          // do type test first to ensure we won't select outer on null
+          if (outerTestNeeded) and(typeTest(testedBinder, expectedTp), outerTest(testedBinder, expectedTp))
+          else typeTest(testedBinder, expectedTp)
+
+        // true when called to type-test the argument to an extractor
+        // don't do any fancy equality checking, just test the type
+        if (extractorArgTypeTest) default
+        else expectedTp match {
+          // TODO: [SPEC] the spec requires `eq` instead of `==` for singleton types
+          // this implies sym.isStable
+          case SingleType(_, sym)                       => and(equalsTest(CODE.REF(sym), testedBinder), typeTest(testedBinder, expectedTp.widen))
+          // must use == to support e.g. List() == Nil
+          case ThisType(sym) if sym.isModule            => and(equalsTest(CODE.REF(sym), testedBinder), typeTest(testedBinder, expectedTp.widen))
+          case ConstantType(const)                      => equalsTest(Literal(const), testedBinder)
+
+          case ThisType(sym)                            => eqTest(This(sym), testedBinder)
+          case ConstantType(Constant(null)) if testedBinder.info.widen <:< AnyRefClass.tpe
+                                                        => eqTest(CODE.NULL, testedBinder)
+
+          // TODO: verify that we don't need to special-case Array
+          // I think it's okay:
+          //  - the isInstanceOf test includes a test for the element type
+          //  - Scala's arrays are invariant (so we don't drop type tests unsoundly)
+          case _ if (expectedTp <:< AnyRefClass.tpe) && !needsTypeTest(testedBinder.info.widen, expectedTp) =>
+            // do non-null check first to ensure we won't select outer on null
+            if (outerTestNeeded) and(nonNullTest(testedBinder), outerTest(testedBinder, expectedTp))
+            else nonNullTest(testedBinder)
+
+          case _ => default
+        }
       }
 
-      val cond = typeAndEqualityTest(patBinder, pt)
-      val res  = codegen._asInstanceOf(patBinder, nextBinderTp)
+      val cond = renderCondition(treeCondStrategy)
+      val res  = codegen._asInstanceOf(testedBinder, nextBinderTp)
 
-      // TODO: remove this
-      def isStraightTypeTest = cond match { case TypeApply(_, _) => cond.symbol == Any_isInstanceOf case _ => false }
+      // is this purely a type test, e.g. no outer check, no equality tests (used in switch emission)
+      def isPureTypeTest = renderCondition(pureTypeTestChecker)
 
-      override def toString = "TET"+(patBinder, pt)
+      override def toString = "TT"+(expectedTp, testedBinder.name, nextBinderTp)
     }
 
     // need to substitute to deal with existential types -- TODO: deal with existentials better, don't substitute (see RichClass during quick.comp)
@@ -1000,7 +1030,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       // 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 = codegen._equals(patTree, prevBinder)
       val res  = CODE.REF(prevBinder)
-      override def toString = "ET"+(prevBinder, patTree)
+      override def toString = "ET"+(prevBinder.name, patTree)
     }
 
     case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders {
@@ -1062,7 +1092,21 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
         def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree)))
         // println("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}")))
 
+        def isSwitchAnnotation(tpe: Type) = tpe hasAnnotation SwitchClass
+        def isUncheckedAnnotation(tpe: Type) = tpe hasAnnotation UncheckedClass
+
+        val (unchecked, requireSwitch) = scrut match {
+          case Typed(_, tpt) =>
+            (isUncheckedAnnotation(tpt.tpe),
+             // matches with two or fewer cases need not apply for switchiness (if-then-else will do)
+             isSwitchAnnotation(tpt.tpe) && casesNoSubstOnly.lengthCompare(2) > 0)
+          case _ =>
+            (false, false)
+        }
+
         emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt, matchFailGenOverride).getOrElse{
+          if (requireSwitch) typer.context.unit.error(scrut.pos, "could not emit switch for @switch annotated match")
+
           if (casesNoSubstOnly nonEmpty) {
             // before optimizing, check casesNoSubstOnly for presence of a default case,
             // since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one
@@ -1077,7 +1121,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
                   }) None
               else matchFailGen
 
-            val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt)
+            val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt, unchecked)
 
             val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, synthCatchAll)
 
@@ -1262,7 +1306,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 // decisions, decisions
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
-  trait TreeMakerApproximation extends TreeMakers { self: CodegenCore =>
+  trait TreeMakerApproximation extends TreeMakers with Prettification{ self: CodegenCore =>
     object Test {
       var currId = 0
     }
@@ -1281,9 +1325,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 
       val id = { Test.currId += 1; Test.currId}
       override def toString =
-        if (cond eq Top) "T"
-        else if(cond eq Havoc) "!?"
-        else "T"+ id + (if(reusedBy nonEmpty) "!["+ treeMaker +"]" else (if(reuses.isEmpty) "["+ treeMaker +"]" else  " cf. T"+reuses.get.id))
+        "T"+ id + "C("+ cond +")"  //+ (reuses map ("== T"+_.id) getOrElse (if(reusedBy.isEmpty) treeMaker else reusedBy mkString (treeMaker+ " -->(", ", ",")")))
     }
 
     object Cond {
@@ -1304,10 +1346,11 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
     }
 
     // does not contribute any knowledge
-    case object Top extends Cond
+    case object Top extends Cond {override def toString = "T"}
+
 
     // takes away knowledge. e.g., a user-defined guard
-    case object Havoc extends Cond
+    case object Havoc extends Cond {override def toString = "_|_"}
 
     // we know everything! everything!
     // this either means the case is unreachable,
@@ -1315,11 +1358,15 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
     // case object Bottom extends Cond
 
 
+    case class AndCond(a: Cond, b: Cond) extends Cond {override def toString = a +"/\\"+ b}
+    case class OrCond(a: Cond, b: Cond) extends Cond  {override def toString = "("+a+") \\/ ("+ b +")"}
+
     object EqualityCond {
       private val uniques = new collection.mutable.HashMap[(Tree, Tree), EqualityCond]
       def apply(testedPath: Tree, rhs: Tree): EqualityCond = uniques getOrElseUpdate((testedPath, rhs), new EqualityCond(testedPath, rhs))
+      def unapply(c: EqualityCond) = Some(c.testedPath, c.rhs)
     }
-    class EqualityCond(testedPath: Tree, rhs: Tree) extends Cond {
+    class EqualityCond(val testedPath: Tree, val rhs: Tree) extends Cond {
       // def negation         = TopCond // inequality doesn't teach us anything
       // do simplification when we know enough about the tree statically:
       //  - collapse equal trees
@@ -1329,103 +1376,181 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       override def toString = testedPath +" == "+ rhs +"#"+ id
     }
 
-    object TypeCond {
-      private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeCond]
-      def apply(testedPath: Tree, pt: Type): TypeCond = uniques getOrElseUpdate((testedPath, pt), new TypeCond(testedPath, pt))
+    object NonNullCond {
+      private val uniques = new collection.mutable.HashMap[Tree, NonNullCond]
+      def apply(testedPath: Tree): NonNullCond = uniques getOrElseUpdate(testedPath, new NonNullCond(testedPath))
+      def unapply(c: NonNullCond) = Some(c.testedPath)
     }
-    class TypeCond(testedPath: Tree, pt: Type) extends Cond {
-      // def negation         = TopCond // inequality doesn't teach us anything
-      // do simplification when we know enough about the tree statically:
-      //  - collapse equal trees
-      //  - accumulate tests when (in)equality not known statically
-      //  - become bottom when we statically know this can never match
-      override def toString = testedPath +" <: "+ pt +"#"+ id
+    class NonNullCond(val testedPath: Tree) extends Cond {
+      override def toString = testedPath +" ne null " +"#"+ id
     }
 
-    object TypeAndEqualityCond {
-      private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeAndEqualityCond]
-      def apply(testedPath: Tree, pt: Type): TypeAndEqualityCond = uniques getOrElseUpdate((testedPath, pt), new TypeAndEqualityCond(testedPath, pt))
+    object TypeCond {
+      private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeCond]
+      def apply(testedPath: Tree, pt: Type): TypeCond = uniques getOrElseUpdate((testedPath, pt), new TypeCond(testedPath, pt))
+      def unapply(c: TypeCond) = Some(c.testedPath, c.pt)
     }
-    class TypeAndEqualityCond(testedPath: Tree, pt: Type) extends Cond {
+    class TypeCond(val testedPath: Tree, val pt: Type) extends Cond {
       // def negation         = TopCond // inequality doesn't teach us anything
       // do simplification when we know enough about the tree statically:
       //  - collapse equal trees
       //  - accumulate tests when (in)equality not known statically
       //  - become bottom when we statically know this can never match
-      override def toString = testedPath +" (<: && ==) "+ pt +"#"+ id
+      override def toString = testedPath +" : "+ pt +"#"+ id
     }
 
-    def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = {
+//    class OuterEqCond(val testedPath: Tree, val expectedType: Type) extends Cond {
+//      val expectedOuter = 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
+//
+//      (Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter
+//    }
+
+
+    // returns (tree, tests), where `tree` will be used to refer to `root` in `tests`
+    abstract class TreeMakersToConds(val root: Symbol, val cases: List[List[TreeMaker]]) {
       // a variable in this set should never be replaced by a tree that "does not consist of a selection on a variable in this set" (intuitively)
-      val pointsToBound            = collection.mutable.HashSet(root)
+      private val pointsToBound            = collection.mutable.HashSet(root)
 
       // the substitution that renames variables to variables in pointsToBound
-      var normalize: Substitution  = EmptySubstitution
+      private var normalize: Substitution  = EmptySubstitution
 
       // replaces a variable (in pointsToBound) by a selection on another variable in pointsToBound
       // TODO check:
       //   pointsToBound -- accumSubst.from == Set(root) && (accumSubst.from.toSet -- pointsToBound) isEmpty
-      var accumSubst: Substitution = EmptySubstitution
+      private var accumSubst: Substitution = EmptySubstitution
+
+      private val trees = new collection.mutable.HashSet[Tree]
 
-      val trees = new collection.mutable.HashSet[Tree]
+      // TODO: improve, e.g., for constants
+      def sameValue(a: Tree, b: Tree): Boolean = (a eq b) || ((a, b) match {
+        case (_ : Ident, _ : Ident) => a.symbol eq b.symbol
+        case _                      => false
+      })
+
+      // hashconsing trees (modulo value-equality)
+      def unique(t: Tree, tpOverride: Type = NoType): Tree =
+        trees find (a => a.equalsStructure0(t)(sameValue)) match {
+          case Some(orig) => orig // println("unique: "+ (t eq orig, orig));
+          case _ =>
+            trees += t
+            if (tpOverride != NoType) t setType tpOverride
+            else t
+        }
 
-      def approximateTreeMaker(tm: TreeMaker): Test = {
-        val subst = tm.substitution
+      def uniqueTp(tp: Type): Type = tp match {
+        // typerefs etc are already hashconsed
+        case _ : UniqueType                      => tp
+        case tp@RefinedType(parents, EmptyScope) => tp.memo(tp: Type)(identity) // TODO: does this help?
+        case _                                   => tp
+      }
 
+      // produce the unique tree used to refer to this binder
+      // the type of the binder passed to the first invocation
+      // determines the type of the tree that'll be returned for that binder as of then
+      def binderToUniqueTree(b: Symbol) =
+        unique(accumSubst(normalize(CODE.REF(b))), b.tpe)
+
+      // note that the sequencing of operations is important: must visit in same order as match execution
+      // binderToUniqueTree uses the type of the first symbol that was encountered as the type for all future binders
+      def treeMakerToCond(tm: TreeMaker): Cond = {
+        updateSubstitution(tm.substitution)
+
+        tm match {
+          case ttm@TypeTestTreeMaker(prevBinder, testedBinder, pt, _)   =>
+            object condStrategy extends TypeTestTreeMaker.TypeTestCondStrategy {
+              type Result                                           = Cond
+              def and(a: Result, b: Result)                         = AndCond(a, b)
+              def outerTest(testedBinder: Symbol, expectedTp: Type) = Top // TODO OuterEqCond(testedBinder, expectedType)
+              def typeTest(b: Symbol, pt: Type)                     = TypeCond(binderToUniqueTree(b), uniqueTp(pt))
+              def nonNullTest(testedBinder: Symbol)                 = NonNullCond(binderToUniqueTree(testedBinder))
+              def equalsTest(pat: Tree, testedBinder: Symbol)       = EqualityCond(binderToUniqueTree(testedBinder), unique(pat))
+              def eqTest(pat: Tree, testedBinder: Symbol)           = EqualityCond(binderToUniqueTree(testedBinder), unique(pat)) // TODO: eq, not ==
+            }
+            ttm.renderCondition(condStrategy)
+          case EqualityTestTreeMaker(prevBinder, patTree, _)        => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree))
+          case AlternativesTreeMaker(_, altss, _)                   => altss map (_ map treeMakerToCond reduceLeft AndCond) reduceLeft OrCond
+          case ProductExtractorTreeMaker(testedBinder, None, subst) => NonNullCond(binderToUniqueTree(testedBinder))
+          case ExtractorTreeMaker(_, _, _, _)
+             | GuardTreeMaker(_)
+             | ProductExtractorTreeMaker(_, Some(_), _)
+             | BodyTreeMaker(_, _)                                  => Havoc
+          case SubstOnlyTreeMaker(_, _)                             => Top
+        }
+      }
+
+      private def updateSubstitution(subst: Substitution) = {
         // find part of substitution that replaces bound symbols by new symbols, and reverse that part
         // so that we don't introduce new aliases for existing symbols, thus keeping the set of bound symbols minimal
         val (boundSubst, unboundSubst) = (subst.from zip subst.to) partition {case (f, t) =>
             t.isInstanceOf[Ident] && (t.symbol ne NoSymbol) && pointsToBound(f)
           }
         val (boundFrom, boundTo) = boundSubst.unzip
+        val (unboundFrom, unboundTo) = unboundSubst.unzip
+
+        // reverse substitution that would otherwise replace a variable we already encountered by a new variable
+        // NOTE: this forgets the more precise we have for these later variables, but that's probably okay
         normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_)))
         // println("normalize: "+ normalize)
 
-        val (unboundFrom, unboundTo) = unboundSubst unzip
         val okSubst = Substitution(unboundFrom, unboundTo map (normalize(_))) // it's important substitution does not duplicate trees here -- it helps to keep hash consing simple, anyway
         pointsToBound ++= ((okSubst.from, okSubst.to).zipped filter { (f, t) => pointsToBound exists (sym => t.exists(_.symbol == sym)) })._1
         // println("pointsToBound: "+ pointsToBound)
 
         accumSubst >>= okSubst
         // println("accumSubst: "+ accumSubst)
+      }
 
-        // TODO: improve, e.g., for constants
-        def sameValue(a: Tree, b: Tree): Boolean = (a eq b) || ((a, b) match {
-          case (_ : Ident, _ : Ident) => a.symbol eq b.symbol
-          case _                      => false
-        })
-
-        // hashconsing trees (modulo value-equality)
-        def unique(t: Tree): Tree =
-          trees find (a => a.equalsStructure0(t)(sameValue)) match {
-            case Some(orig) => orig // println("unique: "+ (t eq orig, orig));
-            case _ => trees += t; t
-          }
+      def approximateTreeMaker(tm: TreeMaker): Test =
+        Test(treeMakerToCond(tm), tm)
 
-        def uniqueTp(tp: Type): Type = tp match {
-          // typerefs etc are already hashconsed
-          case _ : UniqueType                      => tp
-          case tp@RefinedType(parents, EmptyScope) => tp.memo(tp: Type)(identity) // TODO: does this help?
-          case _                                   => tp
-        }
+      def approximateMatch: List[List[Test]] = cases.map { _ map approximateTreeMaker }
+    }
 
-        def binderToUniqueTree(b: Symbol) = unique(accumSubst(normalize(CODE.REF(b))))
+    def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = {
+      object approximator extends TreeMakersToConds(root, cases)
+      approximator.approximateMatch
+    }
 
-        Test(tm match {
-          case ProductExtractorTreeMaker(pb, None, subst)           => Top // TODO: NotNullTest(prevBinder)
-          case tm@TypeTestTreeMaker(prevBinder, nextBinderTp, _)    => TypeCond(binderToUniqueTree(prevBinder), uniqueTp(nextBinderTp))
-          case tm@TypeAndEqualityTestTreeMaker(_, patBinder, pt, _) => TypeAndEqualityCond(binderToUniqueTree(patBinder), uniqueTp(pt))
-          case tm@EqualityTestTreeMaker(prevBinder, patTree, _)     => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree))
-          case ExtractorTreeMaker(_, _, _, _)
-             | GuardTreeMaker(_)
-             | ProductExtractorTreeMaker(_, Some(_), _)             => Havoc
-          case AlternativesTreeMaker(_, _, _)                       => Havoc // TODO: can do better here
-          case SubstOnlyTreeMaker(_, _)                             => Top
-          case BodyTreeMaker(_, _)                                  => Havoc
-        }, tm)
-      }
+    def showTreeMakers(cases: List[List[TreeMaker]]) = {
+      println("treeMakers:")
+      println(alignAcrossRows(cases, ">>"))
+    }
+
+    def showTests(testss: List[List[Test]]) = {
+      println("tests: ")
+      println(alignAcrossRows(testss, "&"))
+    }
+  }
+
+  trait Prettification {
+    private def max(xs: Seq[Int]) = if (xs isEmpty) 0 else xs max
 
-      cases.map { _ map approximateTreeMaker }
+    def alignedColumns(cols: Seq[AnyRef]): Seq[String] = {
+      def toString(x: AnyRef) = if (x eq null) "" else x.toString
+      if (cols.isEmpty || cols.tails.isEmpty) cols map toString
+      else {
+        val (colStrs, colLens) = cols map {c => val s = toString(c); (s, s.length)} unzip
+        val maxLen = max(colLens)
+        val avgLen = colLens.sum/colLens.length
+        val goalLen = maxLen min avgLen*2
+        def pad(s: String) = {
+          val toAdd = ((goalLen - s.length) max 0) + 2
+          (" " * (toAdd/2)) + s + (" " * (toAdd/2 + (toAdd%2)))
+        }
+        cols map (x => pad(toString(x)))
+      }
+    }
+    def alignAcrossRows(xss: List[List[AnyRef]], sep: String, lineSep: String = "\n"): String = {
+      val maxLen = max(xss map (_.length))
+      val padded = xss map (xs => xs ++ List.fill(maxLen - xs.length)(null))
+      padded.transpose.map(alignedColumns).transpose map (_.mkString(sep)) mkString(lineSep)
     }
   }
 
@@ -1446,28 +1571,49 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       // interpret:
       val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]]
       val tested = new collection.mutable.HashSet[Cond]
-      testss foreach { tests =>
-        tested.clear()
-        tests dropWhile { test =>
-          val cond = test.cond
-          if ((cond eq Havoc) || (cond eq Top)) (cond eq Top) // stop when we encounter a havoc, skip top
-          else {
-            tested += cond
+
+      def storeDependencies(test: Test) = {
+        val cond = test.cond
+
+        def simplify(c: Cond): Set[Cond] = c match {
+          case AndCond(a, b) => simplify(a) ++ simplify(b)
+          case OrCond(_, _) => Set(Havoc) // TODO: supremum?
+          case NonNullCond(_) => Set(Top) // not worth remembering
+          case _ => Set(c)
+        }
+        val conds = simplify(cond)
+
+        if (conds(Havoc)) false // stop when we encounter a havoc
+        else {
+          val nonTrivial = conds filterNot (_ == Top)
+          if (nonTrivial nonEmpty) {
+            tested ++= nonTrivial
 
             // is there an earlier test that checks our condition and whose dependencies are implied by ours?
-            dependencies find { case (priorTest, deps) =>
-              ((priorTest.cond eq cond) || (deps contains cond)) && (deps subsetOf tested)
-            } foreach { case (priorTest, deps) =>
-              // if so, note the dependency in both tests
-              priorTest registerReuseBy test
+            dependencies find {
+              case (priorTest, deps) =>
+                ((simplify(priorTest.cond) == nonTrivial) || // our conditions are implied by priorTest if it checks the same thing directly
+                 (nonTrivial subsetOf deps)                  // or if it depends on a superset of our conditions
+                ) && (deps subsetOf tested)             // the conditions we've tested when we are here in the match satisfy the prior test, and hence what it tested
+            } foreach {
+              case (priorTest, _) =>
+                // if so, note the dependency in both tests
+                priorTest registerReuseBy test
             }
 
             dependencies(test) = tested.toSet // copies
-            true
           }
+          true
         }
       }
 
+
+      testss foreach { tests =>
+        tested.clear()
+        tests dropWhile storeDependencies
+      }
+      // println("dependencies: "+ dependencies)
+
       // find longest prefix of tests that reuse a prior test, and whose dependent conditions monotonically increase
       // 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)
@@ -1476,7 +1622,12 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       var okToCall = false
       val reusedOrOrig = (tm: TreeMaker) => {assert(okToCall); reused.getOrElse(tm, tm)}
 
-      val res = testss map { tests =>
+      // maybe collapse: replace shared prefix of tree makers by a ReusingCondTreeMaker
+      // once this has been computed, we'll know which tree makers are reused,
+      // and we'll replace those by the ReusedCondTreeMakers we've constructed (and stored in the reused map)
+      val collapsed = testss map { tests =>
+        // map tests to the equivalent list of treemakers, replacing shared prefixes by a reusing treemaker
+        // if there's no sharing, simply map to the tree makers corresponding to the tests
         var currDeps = Set[Cond]()
         val (sharedPrefix, suffix) = tests span { test =>
           (test.cond eq Top) || (for(
@@ -1487,23 +1638,33 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
                 yield diff).nonEmpty
         }
 
-        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) reusedTest.treeMaker match {
-            case reusedCTM: CondTreeMaker => reused(reusedCTM) = ReusedCondTreeMaker(reusedCTM)
-            case _ =>
-          }
+        val collapsedTreeMakers =
+          if (sharedPrefix.isEmpty) None
+          else { // even sharing prefixes of length 1 brings some benefit (overhead-percentage for compiler: 26->24%, lib: 19->16%)
+            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, reusedOrOrig) :: suffix.map(_.treeMaker)
-        } else None
+            // println("sharedPrefix: "+ sharedPrefix)
+            // if the shared prefix contains interesting conditions (!= Top)
+            // and the last of such interesting shared conditions reuses another treemaker's test
+            // replace the whole sharedPrefix by a ReusingCondTreeMaker
+            for (lastShared <- sharedPrefix.reverse.dropWhile(_.cond eq Top).headOption;
+                 lastReused <- lastShared.reuses)
+              yield ReusingCondTreeMaker(sharedPrefix, reusedOrOrig) :: suffix.map(_.treeMaker)
+          }
 
         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)
+      // replace original treemakers that are reused (as determined when computing collapsed),
+      // by ReusedCondTreeMakers
+      val reusedMakers = collapsed mapConserve (_ mapConserve reusedOrOrig)
+//      println("after CSE:")
+//      showTreeMakers(reusedMakers)
+      reusedMakers
     }
 
     object ReusedCondTreeMaker {
@@ -1520,28 +1681,45 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       // TODO: finer-grained duplication
       def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(codegen eq optimizedCodegen)
         atPos(pos)(casegen.asInstanceOf[optimizedCodegen.OptimizedCasegen].flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate))
+
+      override def toString = "Memo"+(nextBinder.name, storedCond.name, cond, res, substitution)
     }
 
     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
+        // replace binder of each dropped treemaker by corresponding binder bound by the most recent reused treemaker
+        var mostRecentReusedMaker: ReusedCondTreeMaker = null
+        def mapToStored(droppedBinder: Symbol) = if (mostRecentReusedMaker eq null) Nil else List((droppedBinder, REF(mostRecentReusedMaker.nextBinder)))
+        val (from, to) = sharedPrefix.flatMap { dropped =>
+          dropped.reuses.map(test => toReused(test.treeMaker)).foreach {
+            case reusedMaker: ReusedCondTreeMaker =>
+              mostRecentReusedMaker = reusedMaker
+            case _ =>
           }
-        oldSubs.foldLeft(Substitution(from, to))(_ >> _)
+
+          // TODO: have super-trait for retrieving the variable that's operated on by a tree maker
+          // and thus assumed in scope, either because it binds it or because it refers to it
+          dropped.treeMaker match {
+            case dropped: FunTreeMaker =>
+              mapToStored(dropped.nextBinder)
+            case _ => Nil
+          }
+        }.unzip
+        val rerouteToReusedBinders = Substitution(from, to)
+
+        val collapsedDroppedSubst = sharedPrefix map (t => (toReused(t.treeMaker).substitution))
+
+        collapsedDroppedSubst.foldLeft(rerouteToReusedBinders)(_ >> _)
       }
 
-      def chainBefore(next: Tree)(casegen: Casegen): Tree = {
-        val cond = REF(dropped_priors.reverse.collectFirst{case (_, Some(ctm: ReusedCondTreeMaker)) => ctm}.get.storedCond)
+      lazy val lastReusedTreeMaker = sharedPrefix.reverse.flatMap(tm => tm.reuses map (test => toReused(test.treeMaker))).collectFirst{case x: ReusedCondTreeMaker => x}.head
 
-        // 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)
-        casegen.ifThenElseZero(cond, substitution(next).duplicate)
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = {
+        // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift,
+        // and in its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S)
+        casegen.ifThenElseZero(REF(lastReusedTreeMaker.storedCond), substitution(next).duplicate)
       }
+      override def toString = "R"+(lastReusedTreeMaker.storedCond.name, substitution)
     }
   }
 
@@ -1669,10 +1847,8 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       // analyze the result of approximateTreeMaker rather than the TreeMaker itself
       object SwitchableTreeMaker extends SwitchableTreeMakerExtractor {
         def unapply(x: TreeMaker): Option[Tree] = x match {
-          case tm@TypeTestTreeMaker(_, _, _) =>
-            Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(tm.nextBinderTp)) /* not used by back-end */)) //  -- TODO: use this if binder does not occur in the body
-          case tm@TypeAndEqualityTestTreeMaker(_, patBinder, pt, _) if tm.isStraightTypeTest =>
-            Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(tm.nextBinderTp)) /* not used by back-end */))
+          case tm@TypeTestTreeMaker(_, _, pt, _) if tm.isPureTypeTest => //  -- TODO: use this if binder does not occur in the body
+            Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(pt)) /* not used by back-end */))
           case _ =>
             None
         }
@@ -1824,7 +2000,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
                               with DeadCodeElimination
                               with SwitchEmission
                               with OptimizedCodegen { self: TreeMakers =>
-    override def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) = {
+    override def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type, unchecked: Boolean): (List[List[TreeMaker]], List[Tree]) = {
       val optCases = doCSE(prevBinder, doDCE(prevBinder, cases, pt), pt)
       val toHoist = (
         for (treeMakers <- optCases)