further clean up in virtpatmat

farewell ProtoTreeMaker, we hardly knew ye

needed one more repeatedToSeq for pos/annotDepMethType when compiling
under -Xexperimental and -Yvirtpatmat... I wonder why this hadn't failed
before outer check for extractor type test: definitely need it for case
classes, and probably makes sense for user-defined extractors as well

no review

1 files changed, 218 insertions, 228 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index 5c65f554ef..3e9ad1b639 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -49,6 +49,8 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
   private lazy val matchingStrategyTycon = definitions.getClass("scala.MatchingStrategy").typeConstructor
 
   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
+
     import typer._
     import typeDebug.{ ptTree, ptBlock, ptLine }
 
@@ -92,13 +94,13 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         case Match(scrut, cases) =>
           val scrutType = if(scrut.tpe ne null) repeatedToSeq(elimAnonymousClass(scrut.tpe.widen)) else {error("TODO: support match with empty scrut"); NoType} // TODO: ErrorTree
           val scrutSym  = freshSym(tree.pos, scrutType)
-          matchFromCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), pt)
+          matchFromCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), repeatedToSeq(pt)) // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala  with -Xexperimental
         case t => t
       }
 
       // println("before fixerupper: "+ xTree)
       // currentRun.trackerFactory.snapshot()
-      // TODO: do this during tree construction, but that will require tracking the current owner in proto treemakers
+      // 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
       object fixerUpper extends Traverser {
@@ -159,7 +161,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       *      - (for n-ary unapply, n > 1) selection of the i'th tuple component of `x_1`
       *      - (for unapplySeq) x_1.apply(i)
       *
-      *    in the proto-treemakers,
+      *    in the treemakers,
       *
       *    Thus, the result type of `translatePattern_i`'s extractor must conform to `M[(T_1,..., T_n)]`.
       *
@@ -167,27 +169,24 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       *    the transformed patterns from left to right. For every pattern ast node, it produces a transformed ast and
       *    a function that will take care of binding and substitution of the next ast (to the right).
       *
-      *    `makeTreeMakers` takes these pairs and accumulates the substitution from left to right, so that the rightmost substitution (a function from Tree to Tree)
-      *    will substitute each bound pattern variable in the whole case.
       */
     def translateCase(scrutSym: Symbol)(tree: Tree): Tree =
       tree match {
         case CaseDef(pattern, guard, body) =>
-          val treeMakers = makeTreeMakers(translatePattern(scrutSym, pattern) ++ translateGuard(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.caseResult),
           // 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
           // 2) body.tpe is the type of the body after applying the substitution that represents the solution of GADT type inference
           // need the explicit cast in case our substitutions in the body change the type to something that doesn't take GADT typing into account
-          TreeMaker.combine(treeMakers, pmgen.caseResult(body, body.tpe), tree.pos)
+          TreeMaker.combine(translatePattern(scrutSym, pattern) ++ translateGuard(guard), pmgen.caseResult(body, body.tpe), tree.pos)
       }
 
-    def translatePattern(prevBinder: Symbol, patTree: Tree): List[ProtoTreeMaker] = {
-      // a list of ProtoTreeMakers that encode `patTree`, and a list of arguments for recursive invocations of `translatePattern` to encode its subpatterns
-      type TranslationStep = (List[ProtoTreeMaker], List[(Symbol, Tree)])
-      @inline def withSubPats(protoTreeMakers: List[ProtoTreeMaker], subpats: (Symbol, Tree)*): TranslationStep = (protoTreeMakers, subpats.toList)
-      @inline def noFurtherSubPats(protoTreeMakers: ProtoTreeMaker*): TranslationStep = (protoTreeMakers.toList, Nil)
+    def translatePattern(patBinder: Symbol, patTree: Tree): List[TreeMaker] = {
+      // a list of TreeMakers that encode `patTree`, and a list of arguments for recursive invocations of `translatePattern` to encode its subpatterns
+      type TranslationStep = (List[TreeMaker], List[(Symbol, Tree)])
+      @inline def withSubPats(treeMakers: List[TreeMaker], subpats: (Symbol, Tree)*): TranslationStep = (treeMakers, subpats.toList)
+      @inline def noFurtherSubPats(treeMakers: TreeMaker*): TranslationStep = (treeMakers.toList, Nil)
 
       val pos = patTree.pos
 
@@ -195,40 +194,40 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         if (!extractor.isTyped) throw new TypeError(pos, "Could not typecheck extractor call: "+ extractor)
         if (extractor.resultInMonad == ErrorType) throw new TypeError(pos, "Unsupported extractor type: "+ extractor.tpe)
 
-        // `patBinders` are the variables bound by this pattern in the following patterns
-        // patBinders are replaced by references to the relevant part of the extractor's result (tuple component, seq element, the result as-is)
-        val sub@(patBinders, _) = extractor.args map {
-          case BoundSym(b, p) => (b, p)
+        // `subpatBinders` are the variables bound by this pattern in the following patterns
+        // subpatBinders are replaced by references to the relevant part of the extractor's result (tuple component, seq element, the result as-is)
+        val sub@(subpatBinders, _) = extractor.args map {
+          case Bound(b, p) => (b, p)
           case p => (freshSym(pos, prefix = "p"), p)
         } unzip
 
         // 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`)
-        (patBinders, extractor.subPatTypes).zipped foreach { case (b, tp) => b setInfo tp } // println("changing "+ b +" : "+ b.info +" -> "+ tp);
+        (subpatBinders, extractor.subPatTypes).zipped foreach { case (b, tp) => b setInfo tp } // println("changing "+ b +" : "+ b.info +" -> "+ tp);
 
-        // println("translateExtractorPattern checking parameter type: "+ (prevBinder, prevBinder.info.widen, extractor.paramType, prevBinder.info.widen <:< extractor.paramType))
+        // println("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType))
         // example check: List[Int] <:< ::[Int]
         // TODO: extractor.paramType may contain unbound type params (run/t2800, run/t3530)
-        val (typeTestProtoTreeMaker, prevBinderOrCasted) =
-          if(!(prevBinder.info.widen <:< extractor.paramType)) {
+        val (typeTestTreeMaker, patBinderOrCasted) =
+          if (needsTypeTest(patBinder.info.widen, extractor.paramType)) {
             val castedBinder = freshSym(pos, extractor.paramType, "cp")
-            // TODO: what's the semantics for outerchecks on user-defined extractors?
-            val cond = maybeWithOuterCheck(prevBinder, extractor.paramType)(pmgen._isInstanceOf(prevBinder, extractor.paramType))
-            // val cond = genTypeDirectedEquals(prevBinder, prevBinder.info.widen, extractor.paramType) -- this seems to slow down compilation A LOT
-            // chain a cast before the actual extractor call
-            // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case)
-            val typeTestProtoTreeMaker = ProtoTreeMaker(
-              List(pmgen.condCast(cond, prevBinder, extractor.paramType)),
+            // chain a type-testing extractor before the actual extractor call
+            // it tests the type, checks the outer pointer and casts to the expected type
+            // the outer check is mandated by the spec for case classes, but we do it for user-defined unapplies as well
+            // (the prefix of the argument passed to the unapply must equal the prefix of the type of the binder)
+            val typeTestTreeMaker = TreeMaker(
+              List(typeTestingExtractor(patBinder, extractor.paramType)),
               castedBinder,
-              List(prevBinder),
+              // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case)
+              List(patBinder),
               List(CODE.REF(castedBinder)))
 
-            (List(typeTestProtoTreeMaker), castedBinder)
-          } else (Nil, prevBinder)
+            (List(typeTestTreeMaker), castedBinder)
+          } else (Nil, patBinder)
 
         // the extractor call (applied to the binder bound by the flatMap corresponding to the previous (i.e., enclosing/outer) pattern)
-        val extractorApply = atPos(pos)(extractor.spliceApply(prevBinderOrCasted)) // treegen
+        val extractorApply = atPos(pos)(extractor.spliceApply(patBinderOrCasted)) // treegen
 
         val patTreeLifted =
           if(extractor.resultType.typeSymbol == BooleanClass) pmgen.cond(extractorApply)
@@ -236,42 +235,37 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
 
         // println("patTreeLifted= "+ patTreeLifted)
 
-        val binder  = freshSym(pos, extractor.resultInMonad) // can't simplify this when patBinders.isEmpty, since UnitClass.tpe is definitely wrong when extractor.isSeq, and extractor.resultInMonad should always be correct since it comes directly from the extractor's result type
-        val patRefs = if(patBinders isEmpty) Nil else extractor.subPatRefs(binder)
-        val extractorProtoTreeMaker = ProtoTreeMaker(List(patTreeLifted), binder, patBinders, patRefs, extractor.lengthGuard(binder))
-
-        withSubPats(typeTestProtoTreeMaker :+ extractorProtoTreeMaker, sub.zip: _*)
-      }
-
-      object BoundSym {
-        def unapply(t: Tree): Option[(Symbol, Tree)] = t match {
-          case t@Bind(n, p) if (t.symbol ne null) && (t.symbol ne NoSymbol) => // pos/t2429 does not satisfy these conditions
-            Some((t.symbol, p))
-          case _ => None
+        val binder  = freshSym(pos, extractor.resultInMonad) // can't simplify this when subpatBinders.isEmpty, since UnitClass.tpe is definitely wrong when extractor.isSeq, and extractor.resultInMonad should always be correct since it comes directly from the extractor's result type
+        val subpatRefs = if(subpatBinders isEmpty) Nil else extractor.subPatRefs(binder)
+        val extractorTreeMaker = extractor.lengthGuard(binder) match {
+          case None => TreeMaker(List(patTreeLifted), binder, subpatBinders, subpatRefs)
+          case Some(lenGuard) => TreeMaker.filtered(patTreeLifted, lenGuard, binder, subpatBinders, subpatRefs)
         }
+
+        withSubPats(typeTestTreeMaker :+ extractorTreeMaker, sub.zip: _*)
       }
 
       /** Decompose the pattern in `tree`, of shape C(p_1, ..., p_N), into a list of N symbols, and a list of its N sub-trees
         * The list of N symbols contains symbols for every bound name as well as the un-named sub-patterns (fresh symbols are generated here for these)
         *
-        * @arg prevBinder  symbol used to refer to the result of the previous pattern's extractor (will later be replaced by the outer tree with the correct tree to refer to that patterns result)
+        * @arg patBinder  symbol used to refer to the result of the previous pattern's extractor (will later be replaced by the outer tree with the correct tree to refer to that patterns result)
         */
       object MaybeBoundTyped {
         // the returned type is the one inferred by inferTypedPattern (`owntype`)
         def unapply(tree: Tree): Option[(Symbol, Type)] = tree match {
-          case BoundSym(patBinder, typed@Typed(expr, tpt)) => Some((patBinder, typed.tpe))
-          case Bind(_, typed@Typed(expr, tpt))             => Some((prevBinder, typed.tpe))
-          case Typed(expr, tpt)                            => Some((prevBinder, tree.tpe))
+          case Bound(subpatBinder, typed@Typed(expr, tpt)) => Some((subpatBinder, typed.tpe))
+          case Bind(_, typed@Typed(expr, tpt))             => Some((patBinder, typed.tpe))
+          case Typed(expr, tpt)                            => Some((patBinder, tree.tpe))
           case _                                           => None
         }
       }
 
-      (patTree match {
+      val (treeMakers, subpats) = patTree match {
         // skip wildcard trees -- no point in checking them
         case WildcardPattern() => noFurtherSubPats()
         case UnApply(unfun, args) =>
           // TODO: check unargs == args
-          // println("unfun: "+ (unfun.tpe, unfun.symbol.ownerChain, unfun.symbol.info, prevBinder.info))
+          // println("unfun: "+ (unfun.tpe, unfun.symbol.ownerChain, unfun.symbol.info, patBinder.info))
           translateExtractorPattern(ExtractorCall(unfun, args))
 
         /** A constructor pattern is of the form c(p1, ..., pn) where n ≥ 0.
@@ -297,15 +291,15 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
             The type of x is the type pattern T, where each type variable and wildcard is replaced by a fresh, unknown type.
             This pattern matches any value matched by the type pattern T (§8.2); it binds the variable name to that value.
         **/
-        // must treat Typed and Bind together -- we need to know the prevBinder of the Bind pattern to get at the actual type
-        case MaybeBoundTyped(patBinder, tpe) =>
-          val prevTp    = prevBinder.info.widen
+        // 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, tpe) =>
+          val prevTp    = patBinder.info.widen
           val accumType = glb(List(prevTp, tpe))
-          val cond      = genTypeDirectedEquals(prevBinder, prevTp, tpe) // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations)
-          val extractor = atPos(pos)(pmgen.condCast(cond, prevBinder, accumType))
+          val cond      = typeAndEqualityTest(patBinder, prevTp, tpe) // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations)
+          val extractor = atPos(pos)(pmgen.condCast(cond, patBinder, accumType))
 
           // a typed pattern never has any subtrees
-          noFurtherSubPats(ProtoTreeMaker.singleBinderWithTp(patBinder, accumType, extractor))
+          noFurtherSubPats(TreeMaker.singleBinderWithTp(subpatBinder, accumType, extractor))
 
 
         /** A pattern binder x@p consists of a pattern variable x and a pattern p.
@@ -314,15 +308,15 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
             provided the run-time type of v is also an instance of T,  <-- TODO! https://issues.scala-lang.org/browse/SI-1503
             and it binds the variable name to that value.
         **/
-        case BoundSym(patBinder, p)          =>
-          // TreeMaker with empty list of trees only performs the substitution patBinder --> prevBinder
-          // println("rebind "+ patBinder +" to "+ prevBinder)
-          withSubPats(List(ProtoTreeMaker.substOnly(List(patBinder), List(CODE.REF(prevBinder)))),
+        case Bound(subpatBinder, p)          =>
+          // TreeMaker with empty list of trees only performs the substitution subpatBinder --> patBinder
+          // println("rebind "+ subpatBinder +" to "+ patBinder)
+          withSubPats(List(TreeMaker.substOnly(List(subpatBinder), List(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 proto treemaker to replace this symbol by a reference that
+            // 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
-            // must be prevBinder, as patBinder has the wrong info: even if the bind assumes a better type, this is not guaranteed until we cast
-            (prevBinder, p)
+            // 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)
           )
 
         /** 8.1.4 Literal Patterns
@@ -334,30 +328,27 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
               The type of r must conform to the expected type of the pattern.
         **/
         case Literal(Constant(_)) | Ident(_) | Select(_, _) =>
-          val prevTp = prevBinder.info.widen
+          val prevTp = patBinder.info.widen
 
-          // NOTE: generate `patTree == prevBinder`, since the extractor must be in control of the equals method (also, prevBinder may be null)
-          val cond = pmgen._equals(patTree, prevBinder)
+          // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null)
+          val cond = pmgen._equals(patTree, patBinder)
 
           // equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required)
-          val extractor = atPos(pos)(pmgen.cond(cond, CODE.REF(prevBinder), prevTp))
+          val extractor = atPos(pos)(pmgen.cond(cond, CODE.REF(patBinder), prevTp))
 
-          noFurtherSubPats(ProtoTreeMaker.singleBinderWithTp(prevBinder, prevTp, extractor))
+          noFurtherSubPats(TreeMaker.singleBinderWithTp(patBinder, prevTp, extractor))
 
         case Alternative(alts)    =>
           val altTrees = alts map { alt =>
             // one alternative may still generate multiple trees (e.g., an extractor call + equality test)
             // (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers
-            val treeMakers = makeTreeMakers(translatePattern(prevBinder, alt))
-
-            // `one(x) : T` where x is the binder before this pattern, which will be replaced by the binder for the alternative by ProtoTreeMaker.singleBinder below
+            // `one(x) : T` where x is the binder before this pattern, which will be replaced by the binder for the alternative by TreeMaker.singleBinder below
             // T is the widened type of the previous binder -- this ascription is necessary to infer a clean type for `or` -- the alternative combinator -- in the presence of existential types
             // see pos/virtpatmat_exist1.scala
-            val one = pmgen.one(CODE.REF(prevBinder), prevBinder.info.widen)
-            TreeMaker.combine(treeMakers, one, pos)
+            TreeMaker.combine(translatePattern(patBinder, alt), pmgen.one(CODE.REF(patBinder), patBinder.info.widen), pos)
           }
 
-          noFurtherSubPats(ProtoTreeMaker.singleBinder(prevBinder, altTrees : _*))
+          noFurtherSubPats(TreeMaker.singleBinder(patBinder, altTrees : _*))
 
       /* TODO: Paul says about future version: I think this should work, and always intended to implement if I can get away with it.
           case class Foo(x: Int, y: String)
@@ -366,26 +357,29 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           def f(x: Any) = x match { case Foo(x, _) | Bar(x) => x } // x is lub of course.
       */
 
-        case Bind(n, p) => // TODO: remove?
-          noFurtherSubPats() // there's no symbol -- something wrong?
+        case Bind(n, p) => // this happens in certain ill-formed programs, there'll be an error later
+          // println("WARNING: Bind tree with unbound symbol "+ patTree)
+          noFurtherSubPats() // there's no symbol -- something's wrong... don't fail here though (or should we?)
 
         // case Star(x)              => // no need to handle this because it's always a wildcard nested in a bind (?)
         // case x: ArrayValue        => // TODO?
         // case x: This              => // TODO?
 
         case _                       =>
-          error("UNHANDLED pattern: "+ (prevBinder, patTree, patTree.getClass))
+          error("UNHANDLED pattern: "+ (patBinder, patTree, patTree.getClass))
           noFurtherSubPats()
-      }) match {
-        case (protoTreeMakers, subpats) => protoTreeMakers ++ subpats.flatMap {case (binder, pat) => translatePattern(binder, pat)}
+      }
+
+      treeMakers ++ subpats.flatMap { case (binder, pat) =>
+        translatePattern(binder, pat) // recurse on subpatterns
       }
     }
 
-    def translateGuard(guard: Tree): List[ProtoTreeMaker] = {
+    def translateGuard(guard: Tree): List[TreeMaker] = {
       if (guard == EmptyTree) List()
       else {
         val binder = freshSym(guard.pos, UnitClass.tpe)
-        List(ProtoTreeMaker(List(pmgen.guard(guard)), binder))
+        List(TreeMaker(List(pmgen.guard(guard)), binder))
       }
     }
 
@@ -530,9 +524,9 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         else ((1 to nbSubPats) map pmgen.tupleSel(binder))).toList
       }
 
-      def lengthGuard(binder: Symbol)(then: Tree) =
+      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)) then
+        if (!isSeq || (expectedLength < minLenToCheck)) None
         else { import CODE._
           // `binder.lengthCompare(expectedLength)`
           def checkExpectedLength = (seqTree(binder) DOT seqLenCmp)(LIT(expectedLength))
@@ -545,12 +539,37 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
             else             _ INT_== _
 
           // `if (binder != null && $checkExpectedLength [== | >=] 0) then else zero`
-          pmgen.condOpt((seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO), then)
+          Some((seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO))
         }
 
       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))
+    def typeTestingExtractor(binder: Symbol, pt: Type) = pmgen.cond(typeTest(binder, pt), pmgen._asInstanceOf(binder, pt), pt)
 
 
     /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms:
@@ -576,50 +595,30 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1.
     **/
 
-    // TODO: align with spec (as quoted above)
     // 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 genOuterCheck to check the type's prefix
-     def genTypeDirectedEquals(scrut: Symbol, scrutTp: Type, expectedTp: Type): Tree = { import CODE._
-      def isMatchUnlessNull = scrutTp <:< expectedTp && (expectedTp <:< AnyRefClass.tpe)
+    // uses maybeWithOuterCheck to check the type's prefix
+    // TODO: align with spec (as quoted above)
+     def typeAndEqualityTest(scrut: Symbol, scrutTp: Type, expectedTp: 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 isRef             = scrutTp <:< AnyRefClass.tpe
       def genEqualsAndInstanceOf(sym: Symbol): Tree
         = pmgen._equals(REF(sym), scrut) AND pmgen._isInstanceOf(scrut, expectedTp.widen)
 
+      def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe
+      def isMatchUnlessNull = isRefTp(expectedTp) && !needsTypeTest(scrutTp, expectedTp)
+
       expectedTp match {
-          case SingleType(_, sym)                       => genEqualsAndInstanceOf(sym) // assert(sym.isStable) -- yep, this seems to be true, like always
-          case ThisType(sym) if sym.isModule            => genEqualsAndInstanceOf(sym) // List() == Nil
-          case ThisType(sym)                            => REF(scrut) OBJ_EQ This(sym) // TODO: this matches the actual pattern matcher, but why not use equals as in the object case above? (see run/t576)
-          case ConstantType(Constant(null)) if isRef    => REF(scrut) OBJ_EQ NULL
-          case ConstantType(const)                      => pmgen._equals(Literal(const), scrut)
-          case _ if isMatchUnlessNull                   => maybeWithOuterCheck(scrut, expectedTp)(REF(scrut) OBJ_NE NULL)
-          case _                                        => maybeWithOuterCheck(scrut, expectedTp)(pmgen._isInstanceOf(scrut, expectedTp))
+          case SingleType(_, sym)                               => genEqualsAndInstanceOf(sym) // assert(sym.isStable) -- yep, this seems to be true, like always
+          case ThisType(sym) if sym.isModule                    => genEqualsAndInstanceOf(sym) // List() == Nil
+          case ThisType(sym)                                    => REF(scrut) OBJ_EQ This(sym) // TODO: this matches the actual pattern matcher, but why not use equals as in the object case above? (see run/t576)
+          case ConstantType(Constant(null)) if isRefTp(scrutTp) => REF(scrut) OBJ_EQ NULL
+          case ConstantType(const)                              => pmgen._equals(Literal(const), scrut)
+          case _ if isMatchUnlessNull                           => maybeWithOuterCheck(scrut, expectedTp)(REF(scrut) OBJ_NE NULL)
+          case _                                                => typeTest(scrut, expectedTp)
         }
     }
 
-    // first check cond, since that should ensure we're not selecting outer on null
-    def maybeWithOuterCheck(binder: Symbol, expectedTp: Type)(cond: Tree): Tree =
-      if (   !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
-          && needsOuterTest(expectedTp, binder.info, context.owner))
-        pmgen.and(cond, genOuterCheck(binder, expectedTp))
-      else
-        cond
-
-    /** adds a test comparing the dynamic outer to the static outer */
-    def genOuterCheck(binder: Symbol, expectedTp: Type): Tree = { import CODE._
-      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
-      (Select(pmgen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix
-    }
-
     /** A conservative approximation of which patterns do not discern anything.
      * They are discarded during the translation.
      */
@@ -635,36 +634,18 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       }
     }
 
-    // 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(from: List[Symbol], to: List[Tree]): TreeSubst = new Transformer with (Tree => Tree) {
-      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)
-        }
+    object Bound {
+      def unapply(t: Tree): Option[(Symbol, Tree)] = t match {
+        case t@Bind(n, p) if (t.symbol ne null) && (t.symbol ne NoSymbol) => // pos/t2429 does not satisfy these conditions
+          Some((t.symbol, p))
+        case _ => None
       }
-
-      @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)
-
-      def apply(tree: Tree): Tree = transform(tree)  // treegen
     }
   }
 
-  // the intermediate language -- can we make this rich enough to do analyses on (exhaustivity/reachability), without looking at the concrete trees?
-  trait PatternLanguage {
+  trait TreeMakers {
     def matchingMonadType: Type
-
-    def typedSubst(from: List[Symbol], to: List[Tree]): TreeSubst
+    def typedSubst(from: List[Symbol], to: List[Tree]): Transformer
     def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol
 
     // codegen relevant to the structure of the translation (how extractors are combined)
@@ -674,115 +655,102 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       def fun(arg: Symbol, body: Tree): Tree
       def or(f: Tree, as: List[Tree]): Tree
       def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree
+      def condOptimized(c: Tree, then: Tree): Tree
     }
     def pmgen: AbsCodeGen
 
-    // tree makers
-    type TreeSubst = Tree => Tree
-    type TreeXForm = Tree => Tree
 
-    object ProtoTreeMaker {
+    object Substitution {
+      // 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(from, to).transform(tree)
+      // forall t: Tree. this(other(t)) == (this >> other)(t)
+      def >>(other: Substitution): Substitution = {
+        new Substitution(other.from ++ from, other.to.map(apply) ++ to) // a quick benchmarking run indicates the `.map(apply)` is not too costly
+      }
+    }
+
+    object EmptySubstitution extends Substitution(Nil, Nil) {
+      override def apply(tree: Tree): Tree = tree
+      override def >>(other: Substitution): Substitution = other
+    }
+
+    object TreeMaker {
       /**
-       * Make a ProtoTreeMaker that will result in an extractor call specified by `patTrees` (see TreeMaker),
-       * the next ProtoTreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing
+       * Make a TreeMaker that will result in an extractor call specified by `patTrees` (see TreeMaker),
+       * the next TreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing
        * a function with binder `funBinder` over our extractor's result
-       * the function's body is determined by the next ProtoTreeMaker, but it can be transformed by the current proto-treemaker (specified by `xform`)
+       * 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`
        */
-      def apply(patTrees: List[Tree], funBinder: Symbol, from: List[Symbol] = Nil, to: List[Tree] = Nil, xform: TreeXForm = identity[Tree]) = {
-        if(from isEmpty)
-          new ProtoTreeMaker(patTrees, { outerSubst: TreeSubst =>
-              (nestedTree => pmgen.fun(funBinder, outerSubst(xform(nestedTree))), outerSubst)
-          })
-        else
-          new ProtoTreeMaker(patTrees, { outerSubst: TreeSubst =>
-              def nextSubst(tree: Tree): Tree = outerSubst(typedSubst(from, to)(tree))
-              (nestedTree => pmgen.fun(funBinder, nextSubst(xform(nestedTree))), nextSubst)
-          })
-      }
+      def apply(patTrees: List[Tree], funBinder: Symbol, from: List[Symbol] = Nil, to: List[Tree] = Nil): TreeMaker =
+        new StdTreeMakerImpl(Substitution(from, to), patTrees, funBinder)
+
+      def filtered(extractor: Tree, guard: Tree, funBinder: Symbol, from: List[Symbol] = Nil, to: List[Tree] = Nil): TreeMaker =
+        new FilteredTreeMaker(Substitution(from, to), extractor, guard, funBinder)
 
-      def singleBinder(binderToSubst: Symbol, patTrees: Tree*): ProtoTreeMaker =
+      def singleBinder(binderToSubst: Symbol, patTrees: Tree*): TreeMaker =
         singleBinderWithTp(binderToSubst, binderToSubst.info.widen, patTrees : _*)
 
-      def singleBinderWithTp(binderToSubst: Symbol, binderType: Type, patTrees: Tree*): ProtoTreeMaker = { // assert(patTrees.head.pos != NoPosition, "proto-tree for "+(binderToSubst, patTrees.toList))
+      def singleBinderWithTp(binderToSubst: Symbol, binderType: Type, patTrees: Tree*): TreeMaker = { // assert(patTrees.head.pos != NoPosition, "tree for "+(binderToSubst, patTrees.toList))
         val binder = freshSym(patTrees.head.pos, binderType)
-        ProtoTreeMaker(patTrees.toList, binder, List(binderToSubst), List(CODE.REF(binder)))
+        TreeMaker(patTrees.toList, binder, List(binderToSubst), List(CODE.REF(binder)))
       }
 
-      def substOnly(from: List[Symbol], to: List[Tree]) = new ProtoTreeMaker(List(), { outerSubst: TreeSubst =>
-        def nextSubst(tree: Tree): Tree = outerSubst(typedSubst(from, to)(tree))
-        (nestedTree => nextSubst(nestedTree), nextSubst)
-      })
-    }
-
-    /**
-     * substTreeMaker: takes a subst and returns the following pair:
-     *   - a transform that wraps a one-argument Function around a tree
-     *     and that replaces the binders that referred to subpatterns in that tree
-     *     by the corresponding selection on the function's argument (a tuple selection, a seq-index, or a seq-drop)
-     *   - the substitution to be applied by the next proto-tree maker
-     *
-     * TODO: can we get rid of ProtoTreeMaker, and just have TreeMaker?
-     */
-    case class ProtoTreeMaker(extractors: List[Tree], substTreeMaker: TreeSubst => (TreeXForm, TreeSubst)) {
-      def threadSubst(subst: TreeSubst): (TreeMaker, TreeSubst) = {
-        val (nestedTreeMaker, newSubst) = substTreeMaker(subst)
-        (TreeMaker(extractors, nestedTreeMaker), newSubst)
+      def substOnly(from: List[Symbol], to: List[Tree]): TreeMaker =
+        new StdTreeMakerImpl(Substitution(from, to))
+
+      // a foldLeft to accumulate the substitution left-to-right, but written using a map and a var for clarity
+      private def propagateSubstitution(treeMakers: List[TreeMaker]): List[TreeMaker] = {
+        var accumSubst: Substitution = EmptySubstitution
+        treeMakers map { maker =>
+          // could mutate maker instead, but it doesn't seem to shave much time off of quick.comp
+          val newMaker = maker withOuterSubstitution accumSubst
+          accumSubst = newMaker.substitution
+          newMaker
+        }
       }
+
+      def combine(treeMakers: List[TreeMaker], body: Tree, pos: Position) =
+        atPos(pos)(propagateSubstitution(treeMakers).foldRight (body) (_ chainBefore _))
     }
 
-    // (o => (o(foo), newO)) :: (o => (o(foo), newO')) :: (o => (o(foo), newO'')) :: (o => (o(foo), newO'''))
-    // (identity(foo), newO) :: (newO(foo), newO') :: (newO'(foo), newO'') :: (newO''(foo), newO''')
-    def makeTreeMakers(protoTreeMakers: List[ProtoTreeMaker]): List[TreeMaker] = {
-      // run the state monad (subst is the state) and get out a list of TreeMakers
-      val (treeMakers, subst) = protoTreeMakers.foldLeft((List[TreeMaker](), identity[Tree](_))){
-        case ((accumTreeMakers, accumSubst), protoTreeMaker) =>
-          val (treeMaker, newSubst) = protoTreeMaker threadSubst accumSubst
-          (treeMaker :: accumTreeMakers, newSubst)
-      }
+    abstract class TreeMaker(val substitution: Substitution, funBinder: Symbol = NoSymbol) {
+      def withOuterSubstitution(outerSubst: Substitution): TreeMaker
 
-      treeMakers.reverse
-    }
+      // build Tree that chains `next` after the current extractor
+      def chainBefore(next: Tree): Tree
 
-    object TreeMaker {
-      /**
-       * Construct a TreeMaker given the trees that represent the extractor call
-       * and the transformation to be transformed on the trees of the sub-patterns
-       * meaning of `trees`:
-       *   - none: only doing substitution,
-       *   - one: a regular extractor call,
-       *   - many: alternatives to be fused by MatchingStrategy.or
-       */
-      def apply(trees: List[Tree], genFunAndSubst0: TreeXForm): TreeMaker = trees match {
-        case Nil        => new NoTreeMaker{def genFunAndSubst(next: Tree) = genFunAndSubst0(next)}
-        case List(tree) => new SingleTreeMaker(tree){def genFunAndSubst(next: Tree) = genFunAndSubst0(next)}
-        case _          => new AlternativeTreeMaker(trees){def genFunAndSubst(next: Tree) = genFunAndSubst0(next)}
+      // wrap a Fun (with binder funBinder) around the next tree (unless funBinder == NoSymbol) and perform our substitution
+      protected def wrapFunSubst(next: Tree): Tree = funBinder match {
+        case NoSymbol => substitution(next)
+        case b => pmgen.fun(b, substitution(next))
       }
-
-      def combine(treeMakers: List[TreeMaker], body: Tree, pos: Position) =
-        atPos(pos)(treeMakers.foldRight (body) (_ genFlatMap _))
     }
 
-    abstract class TreeMaker {
-      // wrap a Fun (with binder x) around the next tree and do aggregated substitution (which
-      // replaces old pattern bindings by the appropriate tuple element selection on the new binders,
-      // that is, `x`, if it was bound by the immediately enclosing pattern)
-      def genFunAndSubst(next: Tree): Tree
+    // TODO: factor out in SubstTreeMaker, SingleTreeMaker, AltTreeMaker?
+    class StdTreeMakerImpl(substitution: Substitution, extractors: List[Tree] = Nil, funBinder: Symbol = NoSymbol) extends TreeMaker(substitution, funBinder) {
+      def withOuterSubstitution(outerSubst: Substitution): StdTreeMakerImpl =
+        new StdTreeMakerImpl(outerSubst >> substitution, extractors, funBinder)
 
       // build Tree that chains `next` after the current extractor
-      def genFlatMap(next: Tree): Tree
-    }
-
-    abstract class NoTreeMaker extends TreeMaker {
-      def genFlatMap(tree: Tree) = genFunAndSubst(tree) // doesn't make a fun, only does substitution
+      def chainBefore(next: Tree): Tree = extractors match {
+        case Nil => wrapFunSubst(next)
+        case List(extractor) => pmgen.flatMap(extractor, wrapFunSubst(next)) setPos extractor.pos
+        case alts => pmgen.or(wrapFunSubst(next), alts) setPos alts.head.pos
+      }
     }
 
-    abstract class SingleTreeMaker(extractor: Tree) extends TreeMaker {
-      def genFlatMap(tree: Tree) = pmgen.flatMap(extractor, genFunAndSubst(tree)) setPos extractor.pos
-    }
+    class FilteredTreeMaker(substitution: Substitution, extractor: Tree, guard: Tree, funBinder: Symbol) extends TreeMaker(substitution, funBinder) {
+      def withOuterSubstitution(outerSubst: Substitution): FilteredTreeMaker =
+        new FilteredTreeMaker(outerSubst >> substitution, extractor, guard, funBinder)
 
-    abstract class AlternativeTreeMaker(alts: List[Tree]) extends TreeMaker {
-      def genFlatMap(tree: Tree) = pmgen.or(genFunAndSubst(tree), alts) setPos alts.head.pos
+      def chainBefore(next: Tree): Tree =
+        pmgen.flatMap(extractor, wrapFunSubst(pmgen.condOptimized(guard, next))) setPos extractor.pos
     }
 
     def matchFromCases(scrut: Tree, scrutSym: Symbol, cases: List[Tree], pt: Type): Tree = {
@@ -793,8 +761,31 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
   }
 
   // generate actual trees
-  trait MatchCodeGen extends PatternLanguage {
+  trait MatchCodeGen extends TreeMakers {
     def matchingStrategy: Tree
+    def typed(tree: Tree, mode: Int, pt: Type): Tree // implemented in MatchTranslator
+
+    // 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(from: List[Symbol], to: List[Tree]): Transformer = 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)
+        }
+      }
+
+      @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)
+    }
 
     lazy val pmgen: CommonCodeGen with MatchingStrategyGen with MonadInstGen =
       if (matchingMonadType.typeSymbol eq OptionClass) (new CommonCodeGen with MatchingStrategyGenOpt with MonadInstGenOpt {})
@@ -859,8 +850,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       // an internal guard TODO: use different method call so exhaustiveness can distinguish it from user-defined guards
       def cond(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = genTypeApply((matchingStrategy DOT vpmName.guard), repackExistential(tp)) APPLY (c, then) // matchingStrategy.guard(c, then)
       def condCast(c: Tree, binder: Symbol, expectedTp: Type): Tree = cond(c, _asInstanceOf(binder, expectedTp), expectedTp)
-      def condOpt(c: Tree, then: Tree): Tree                        = IF (c) THEN then ELSE zero
-      // def cast(expectedTp: Type, binder: Symbol): Tree           = typedGuard( _isInstanceOf(binder, expectedTp), expectedTp, binder)
+      def condOptimized(c: Tree, then: Tree): Tree                  = IF (c) THEN then ELSE zero
     }
 
     trait MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
@@ -874,7 +864,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
     // 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
     trait MatchingStrategyGenOpt extends MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
-      override def guard(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = condOpt(c, one(then, repackExistential(tp)))
+      override def guard(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = condOptimized(c, one(then, repackExistential(tp)))
     }
 
     trait MonadInstGenOpt extends MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
@@ -888,7 +878,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
 
           BLOCK(
             v,
-            IF (vs DOT isEmpty) THEN zero ELSE typedSubst(List(x.symbol), List(vs DOT get))(body)
+            IF (vs DOT isEmpty) THEN zero ELSE typedSubst(List(x.symbol), List(vs DOT get)).transform(body)
           )
         case _ => println("huh?")
           (opt DOT vpmName.flatMap)(fun)