behold ExtractorCall: encapsulating extractors

also, moving more codegen out of translation and into codegen in
preparation of making codegen suitable for analysis

no review, though I'm sure extempore will be all over this

1 files changed, 222 insertions, 202 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index 33d9de9a26..9fd509a48f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -8,8 +8,6 @@ package typechecker
 
 import symtab._
 import Flags.{ CASE => _, _ }
-import scala.collection.mutable.ListBuffer
-
 
 
 /** Translate pattern matching into method calls (these methods form a zero-plus monad), similar in spirit to how for-comprehensions are compiled.
@@ -99,11 +97,7 @@ 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)
-          // when specified, need to propagate pt explicitly, type inferencer can't handle it
-          val optPt = if(!isFullyDefined(pt)) NoType else appliedType(matchingMonadType, List(pt))
-          pmgen.runOrElse(scrut,
-                      pmgen.fun(scrutSym,
-                            ((cases map translateCase(scrutSym)) ++ List(pmgen.zero)) reduceLeft pmgen.typedOrElse(optPt)))
+          pmgen.matchFromCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), pt)
         case t => t
       }
 
@@ -185,76 +179,50 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       tree match {
         case CaseDef(pattern, guard, body) =>
           val treeMakers = makeTreeMakers(translatePattern(scrutSym, pattern) ++ translateGuard(guard))
-          val translatedBody = translateBody(body)
-          TreeMaker.combine(treeMakers, translatedBody, tree.pos)
-          // TODO: if we want to support a generalisation of Kotlin's patmat continue, must not hard-wire lifting into the monad (pmgen.one), so that user can generate failure when needed -- use implicit conversion to lift into monad on-demand
+          // TODO: 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
+          TreeMaker.combine(treeMakers, pmgen.caseResult(body, body.tpe), tree.pos)
       }
 
-    def translateBody(body: Tree) = {
-      // 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
-      pmgen.caseResult(pmgen._asInstanceOf(body, body.tpe))
-    }
-
     def translatePattern(prevBinder: Symbol, patTree: Tree): List[ProtoTreeMaker] = {
-      @inline def withSubPats(protoTreeMakers: List[ProtoTreeMaker], subpats: (Symbol, Tree)*) = (protoTreeMakers, subpats.toList)
-      @inline def noFurtherSubPats(protoTreeMakers: ProtoTreeMaker*) = (protoTreeMakers.toList, Nil)
+      // 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)
 
       val pos = patTree.pos
 
-      def translateExtractorPattern(extractorCallIncludingDummy: Tree, args: List[Tree]): (List[ProtoTreeMaker], List[(Symbol, Tree)]) = {
-        val Some(Apply(extractorCall, _)) = extractorCallIncludingDummy.find{ case Apply(_, List(Ident(nme.SELECTOR_DUMMY))) => true case _ => false }
-
-        if((extractorCall.tpe eq NoType) || !extractorCall.isTyped)
-          throw new TypeError(pos, "Could not typecheck extractor call: "+ extractorCall +": "+ extractorCall.tpe +" (symbol= "+ extractorCall.symbol +").")
-
-        val extractorType = extractorCall.tpe
-        val isSeq = extractorCall.symbol.name == nme.unapplySeq
-
-        // what's the extractor's result type in the monad?
-        val typeInMonad = extractorResultInMonad(extractorType)
-
-        if(typeInMonad == ErrorType) {
-          throw new TypeError(pos, "Unsupported extractor type: "+ extractorType)
-          return noFurtherSubPats()
-        }
+      def translateExtractorPattern(extractor: ExtractorCall): TranslationStep = {
+        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, _) = args map {
+        val sub@(patBinders, _) = extractor.args map {
           case BoundSym(b, p) => (b, p)
           case p => (freshSym(pos, prefix = "p"), p)
         } unzip
 
-        // the types for the binders corresponding to my subpatterns
-        // subPatTypes != args map (_.tpe) since the args may have more specific types than the constructor's parameter types
-        val nbSubPats = args.length
-        val lastIsStar = (nbSubPats > 0) && treeInfo.isStar(args.last)
-        val (subPatTypes, subPatRefs, lenGuard) = monadTypeToSubPatTypesAndRefs(typeInMonad, nbSubPats, isSeq, lastIsStar)
-
         // 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, subPatTypes).zipped foreach { case (b, tp) => b setInfo tp } // println("changing "+ b +" : "+ b.info +" -> "+ tp);
-
-        val extractorParamType = extractorType.paramTypes.head
+        (patBinders, extractor.subPatTypes).zipped foreach { case (b, tp) => b setInfo tp } // println("changing "+ b +" : "+ b.info +" -> "+ tp);
 
-        // println("translateExtractorPattern (subPatTypes, typeInMonad, prevBinder, prevBinder.info.widen, extractorCall.symbol, extractorType, prevBinder.info.widen <:< extractorParamType) =\n"+
-        //   (subPatTypes, typeInMonad, prevBinder, prevBinder.info.widen, extractorCall.symbol, extractorType, prevBinder.info.widen <:< extractorParamType))
-
-        // println("translateExtractorPattern checking parameter type: "+ (prevBinder, prevBinder.info.widen, extractorParamType, prevBinder.info.widen <:< extractorParamType))
+        // println("translateExtractorPattern checking parameter type: "+ (prevBinder, prevBinder.info.widen, extractor.paramType, prevBinder.info.widen <:< extractor.paramType))
         // example check: List[Int] <:< ::[Int]
-        // TODO: extractorParamType may contain unbound type params (run/t2800, run/t3530)
+        // TODO: extractor.paramType may contain unbound type params (run/t2800, run/t3530)
         val (typeTestProtoTreeMaker, prevBinderOrCasted) =
-          if(!(prevBinder.info.widen <:< extractorParamType)) {
-            val castedBinder = freshSym(pos, extractorParamType, "cp")
+          if(!(prevBinder.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, extractorParamType)(pmgen._isInstanceOf(CODE.REF(prevBinder), extractorParamType))
-            // val cond = genTypeDirectedEquals(prevBinder, prevBinder.info.widen, extractorParamType) -- this seems to slow down compilation A LOT
+            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)
             (
-              List(ProtoTreeMaker(List(pmgen.typedGuard(cond, extractorParamType, prevBinder)), { outerSubst: TreeSubst =>
+              List(ProtoTreeMaker(List(pmgen.condCast(cond, prevBinder, extractor.paramType)), { outerSubst: TreeSubst =>
                 val theSubst = typedSubst(List(prevBinder), List(CODE.REF(castedBinder)))
                 def nextSubst(tree: Tree): Tree = outerSubst(theSubst(tree))
                 (nestedTree => pmgen.fun(castedBinder, nextSubst(nestedTree)), nextSubst)})),
@@ -262,18 +230,11 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
             )
           } else (Nil, prevBinder)
 
-        object spliceExtractorApply extends Transformer {
-          override def transform(t: Tree) = t match {
-            case Apply(x, List(Ident(nme.SELECTOR_DUMMY))) =>
-              treeCopy.Apply(t, x, List(CODE.REF(prevBinderOrCasted)))
-            case _ => super.transform(t)
-          }
-        }
         // the extractor call (applied to the binder bound by the flatMap corresponding to the previous (i.e., enclosing/outer) pattern)
-        val extractorApply = atPos(pos)(spliceExtractorApply.transform(extractorCallIncludingDummy)) // treegen
+        val extractorApply = atPos(pos)(extractor.spliceApply(prevBinderOrCasted)) // treegen
 
         val patTreeLifted =
-          if(extractorType.finalResultType.typeSymbol == BooleanClass) pmgen.guard(extractorApply)
+          if(extractor.resultType.typeSymbol == BooleanClass) pmgen.cond(extractorApply)
           else extractorApply
 
         // println("patTreeLifted= "+ patTreeLifted)
@@ -281,15 +242,15 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         val extractorProtoTreeMaker = ProtoTreeMaker(List(patTreeLifted),
           if(patBinders isEmpty)
             { outerSubst: TreeSubst =>
-                val binder = freshSym(pos, typeInMonad) // UnitClass.tpe is definitely wrong when isSeq, and typeInMonad should always be correct since it comes directly from the extractor's result type
-                (nestedTree => pmgen.fun(binder, lenGuard(binder, outerSubst(nestedTree))), outerSubst)
+                val binder = freshSym(pos, extractor.resultInMonad) // 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
+                (nestedTree => pmgen.fun(binder, extractor.lengthGuard(binder, outerSubst(nestedTree))), outerSubst)
             }
           else
             { outerSubst: TreeSubst =>
-                val binder   = freshSym(pos, typeInMonad)
-                val theSubst = typedSubst(patBinders, subPatRefs(binder))
+                val binder   = freshSym(pos, extractor.resultInMonad)
+                val theSubst = typedSubst(patBinders, extractor.subPatRefs(binder))
                 def nextSubst(tree: Tree): Tree = outerSubst(theSubst(tree))
-                (nestedTree => pmgen.fun(binder, lenGuard(binder, nextSubst(nestedTree))), nextSubst)
+                (nestedTree => pmgen.fun(binder, extractor.lengthGuard(binder, nextSubst(nestedTree))), nextSubst)
             })
 
         withSubPats(typeTestProtoTreeMaker :+ extractorProtoTreeMaker, sub.zip: _*)
@@ -318,18 +279,13 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         }
       }
 
-      def unwrapExtractorApply(t: Tree)(implicit extractor: Symbol): Tree = t match {
-        case Apply(x, _) => unwrapExtractorApply(x) // could be implicit arg apply
-        case x if x.symbol == extractor => x
-      }
-
       (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))
-          translateExtractorPattern(unfun, args)
+          translateExtractorPattern(ExtractorCall(unfun, args))
 
         /** A constructor pattern is of the form c(p1, ..., pn) where n ≥ 0.
           It consists of a stable identifier c, followed by element patterns p1, ..., pn.
@@ -345,48 +301,9 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           A special case arises when c’s formal parameter types end in a repeated parameter. This is further discussed in (§8.1.9).
         **/
         case Apply(fun, args)     =>
-          // undo rewrite performed in (5) of adapt
-          val orig      = fun match {case tpt: TypeTree => tpt.original case _ => fun}
-          val origSym   = orig.symbol
-          val extractor = unapplyMember(origSym.filter(sym => reallyExists(unapplyMember(sym.tpe))).tpe)
-
-          if((fun.tpe eq null) || fun.tpe.isError || (extractor eq NoSymbol)) {
-             error("cannot find unapply member for "+ fun +" with args "+ args) // TODO: ErrorTree
-             noFurtherSubPats()
-          } else {
-            // this is a tricky balance: pos/t602.scala, pos/sudoku.scala, run/virtpatmat_alts.scala must all be happy
-            // bypass typing at own risk: val extractorCall = Select(orig, extractor) setType caseClassApplyToUnapplyTp(fun.tpe)
-            // can't always infer type arguments (pos/t602):
-            /*  case class Span[K <: Ordered[K]](low: Option[K]) {
-                  override def equals(x: Any): Boolean = x match {
-                    case Span((low0 @ _)) if low0 equals low => true
-                  }
-                }*/
-            // so... leave undetermined type params floating around if we have to, but forego type-safe substitution when overrideUnsafe
-            // (if we don't infer types, uninstantiated type params show up later: pos/sudoku.scala)
-            // (see also run/virtpatmat_alts.scala)
-            val savedUndets = context.undetparams
-            val extractorCall = try {
-              context.undetparams = Nil
-              silent(_.typed(Apply(Select(orig, extractor), List(Ident(nme.SELECTOR_DUMMY) setType fun.tpe.finalResultType)), EXPRmode, WildcardType), reportAmbiguousErrors = false) match {
-                case extractorCall: Tree => extractorCall // if !extractorCall.containsError()
-                case _ =>
-                  // this fails to resolve overloading properly...
-                  // Apply(typedOperator(Select(orig, extractor)), List(Ident(nme.SELECTOR_DUMMY))) // no need to set the type of the dummy arg, it will be replaced anyway
-
-                  overrideUnsafe = true // all bets are off when you have unbound type params floating around
-                  // println("funtpe after = "+ fun.tpe.finalResultType)
-                  // println("orig: "+(orig, orig.tpe))
-                  val tgt = typed(orig, EXPRmode | QUALmode | POLYmode, HasMember(extractor.name)) // can't specify fun.tpe.finalResultType as the type for the extractor's arg,
-                  // as it may have been inferred incorrectly (see t602, where it's  com.mosol.sl.Span[Any], instead of  com.mosol.sl.Span[?K])
-                  // println("tgt = "+ (tgt, tgt.tpe))
-                  val oper = typed(Select(tgt, extractor.name), EXPRmode | FUNmode | POLYmode | TAPPmode, WildcardType)
-                  // println("oper: "+ (oper, oper.tpe))
-                  Apply(oper, List(Ident(nme.SELECTOR_DUMMY))) // no need to set the type of the dummy arg, it will be replaced anyway
-              }
-            } finally context.undetparams = savedUndets
-
-            translateExtractorPattern(extractorCall, args)
+          ExtractorCall.fromCaseClass(fun, args) map translateExtractorPattern getOrElse {
+            error("cannot find unapply member for "+ fun +" with args "+ args) // TODO: ErrorTree
+            noFurtherSubPats()
           }
 
         /** A typed pattern x : T consists of a pattern variable x and a type pattern T.
@@ -398,7 +315,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           val prevTp    = prevBinder.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.typedGuard(cond, accumType, prevBinder))
+          val extractor = atPos(pos)(pmgen.condCast(cond, prevBinder, accumType))
 
           // a typed pattern never has any subtrees
           noFurtherSubPats(ProtoTreeMaker.singleBinderWithTp(patBinder, accumType, unsafe = true, extractor))
@@ -444,7 +361,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           val cond = pmgen._equals(patTree, prevBinder)
 
           // 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.guard(cond, CODE.REF(prevBinder), prevTp))
+          val extractor = atPos(pos)(pmgen.cond(cond, CODE.REF(prevBinder), prevTp))
 
           noFurtherSubPats(ProtoTreeMaker.singleBinderWithTp(prevBinder, prevTp, unsafe = false, extractor))
 
@@ -485,6 +402,8 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
     def translateGuard(guard: Tree): List[ProtoTreeMaker] = {
       if (guard == EmptyTree) List()
       else List(
+        // TODO: distinguish this tree from more general guards (maybe call those "filter")
+        // the user-supplied guard should not be considered during exhaustiveness/reachable code analysis, the filters should
         ProtoTreeMaker(List(pmgen.guard(guard)),
           { outerSubst =>
             val binder = freshSym(guard.pos, UnitClass.tpe)
@@ -492,51 +411,134 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           }))
     }
 
-// analyzing types, deriving trees from them
-    // turn an extractor's result type into something `monadTypeToSubPatTypesAndRefs` understands
-    def extractorResultInMonad(extractorTp: Type): Type = if(!hasLength(extractorTp.paramTypes, 1)) ErrorType else {
-      val res = extractorTp.finalResultType
-      if(res.typeSymbol == BooleanClass) UnitClass.tpe
-      else {
-        val monadArgs = res.baseType(matchingMonadType.typeSymbol).typeArgs
-        // assert(monadArgs.length == 1, "unhandled extractor type: "+ extractorTp) // TODO: overloaded unapply??
-        if(monadArgs.length == 1) monadArgs(0)
-        else ErrorType
+
+// helper methods: they analyze types and trees in isolation, but they are not (directly) concerned with the structure of the overall translation
+    object ExtractorCall {
+      def apply(unfun: Tree, args: List[Tree]): ExtractorCall = new ExtractorCall(unfun, args)
+
+      // generate a call to the (synthetically generated) extractor of a case class
+      // NOTE: it's an apply, not a select, since in general an extractor call may have multiple argument lists (including an implicit one)
+      // that we need to preserve, so we supply the scrutinee as Ident(nme.SELECTOR_DUMMY),
+      // and replace that dummy by a reference to the actual binder in translateExtractorPattern
+      def fromCaseClass(fun: Tree, args: List[Tree]): Option[ExtractorCall] = {
+        // undo rewrite performed in (5) of adapt
+        val orig      = fun match {case tpt: TypeTree => tpt.original case _ => fun}
+        val origSym   = orig.symbol
+        val extractor = unapplyMember(origSym.filter(sym => reallyExists(unapplyMember(sym.tpe))).tpe)
+
+        if((fun.tpe eq null) || fun.tpe.isError || (extractor eq NoSymbol)) {
+          None
+        } else {
+          // this is a tricky balance: pos/t602.scala, pos/sudoku.scala, run/virtpatmat_alts.scala must all be happy
+          // bypass typing at own risk: val extractorCall = Select(orig, extractor) setType caseClassApplyToUnapplyTp(fun.tpe)
+          // can't always infer type arguments (pos/t602):
+          /*  case class Span[K <: Ordered[K]](low: Option[K]) {
+                override def equals(x: Any): Boolean = x match {
+                  case Span((low0 @ _)) if low0 equals low => true
+                }
+              }*/
+          // so... leave undetermined type params floating around if we have to, but forego type-safe substitution when overrideUnsafe
+          // (if we don't infer types, uninstantiated type params show up later: pos/sudoku.scala)
+          // (see also run/virtpatmat_alts.scala)
+          val savedUndets = context.undetparams
+          val extractorCall = try {
+            context.undetparams = Nil
+            silent(_.typed(Apply(Select(orig, extractor), List(Ident(nme.SELECTOR_DUMMY) setType fun.tpe.finalResultType)), EXPRmode, WildcardType), reportAmbiguousErrors = false) match {
+              case extractorCall: Tree => extractorCall // if !extractorCall.containsError()
+              case _ =>
+                // this fails to resolve overloading properly...
+                // Apply(typedOperator(Select(orig, extractor)), List(Ident(nme.SELECTOR_DUMMY))) // no need to set the type of the dummy arg, it will be replaced anyway
+
+                overrideUnsafe = true // all bets are off when you have unbound type params floating around
+                // println("funtpe after = "+ fun.tpe.finalResultType)
+                // println("orig: "+(orig, orig.tpe))
+                val tgt = typed(orig, EXPRmode | QUALmode | POLYmode, HasMember(extractor.name)) // can't specify fun.tpe.finalResultType as the type for the extractor's arg,
+                // as it may have been inferred incorrectly (see t602, where it's  com.mosol.sl.Span[Any], instead of  com.mosol.sl.Span[?K])
+                // println("tgt = "+ (tgt, tgt.tpe))
+                val oper = typed(Select(tgt, extractor.name), EXPRmode | FUNmode | POLYmode | TAPPmode, WildcardType)
+                // println("oper: "+ (oper, oper.tpe))
+                Apply(oper, List(Ident(nme.SELECTOR_DUMMY))) // no need to set the type of the dummy arg, it will be replaced anyway
+            }
+          } finally context.undetparams = savedUndets
+
+          Some(this(extractorCall, args)) // TODO: simplify spliceApply?
+        }
       }
     }
 
-    // given the type in the monad,
-    // - what are the types for the subpatterns of this extractor,
-    // - how do I select them (in terms of the binder that references the extractors result), and
-    // - what's the length guard (only relevant if `isSeq`)
-    // require (nbSubPats > 0 && (!lastIsStar || isSeq))
-    def monadTypeToSubPatTypesAndRefs(typeInMonad: Type, nbSubPats: Int, isSeq: Boolean, lastIsStar: Boolean): (List[Type], Symbol => List[Tree], (Symbol, Tree) => Tree) = {
-      val ts =
-        if(typeInMonad.typeSymbol eq UnitClass) Nil
-        else if(nbSubPats == 1) List(typeInMonad)
-        else getProductArgs(typeInMonad) match { case Nil => List(typeInMonad) case x => x }
+    class ExtractorCall(extractorCallIncludingDummy: Tree, val args: List[Tree]) {
+      private lazy val Some(Apply(extractorCall, _)) = extractorCallIncludingDummy.find{ case Apply(_, List(Ident(nme.SELECTOR_DUMMY))) => true case _ => false }
+
+      def tpe        = extractorCall.tpe
+      def isTyped    = (tpe ne NoType) && extractorCall.isTyped
+      def resultType = tpe.finalResultType
+      def paramType  = tpe.paramTypes.head
+
+      // what's the extractor's result type in the monad?
+      // turn an extractor's result type into something `monadTypeToSubPatTypesAndRefs` understands
+      lazy val resultInMonad: Type = if(!hasLength(tpe.paramTypes, 1)) ErrorType else {
+        if(resultType.typeSymbol == BooleanClass) UnitClass.tpe
+        else {
+          val monadArgs = resultType.baseType(matchingMonadType.typeSymbol).typeArgs
+          // assert(monadArgs.length == 1, "unhandled extractor type: "+ extractorTp) // TODO: overloaded unapply??
+          if(monadArgs.length == 1) monadArgs(0)
+          else ErrorType
+        }
+      }
 
-      // replace last type (of shape Seq[A]) with RepeatedParam[A] so that formalTypes will
-      // repeat the last argument type to align the formals with the number of arguments
-      val subPatTypes = if(isSeq) {
-        val TypeRef(pre, SeqClass, args) = (ts.last baseType SeqClass)
-        formalTypes(ts.init :+ typeRef(pre, RepeatedParamClass, args), nbSubPats)
-      } else ts
+      def isSeq                            = extractorCall.symbol.name == nme.unapplySeq
+      lazy val nbSubPats                   = args.length
+      lazy val lastIsStar                  = (nbSubPats > 0) && treeInfo.isStar(args.last)
 
-      // println("subPatTypes (typeInMonad, isSeq, nbSubPats, ts, subPatTypes)= "+(typeInMonad, isSeq, nbSubPats, ts, subPatTypes))
-      // only relevant if isSeq: (here to avoid capturing too much in the returned closure)
-      val firstIndexingBinder           = ts.length - 1 // ts.last is the Seq, thus there are `ts.length - 1` non-seq elements in the tuple
-      val lastIndexingBinder            = if(lastIsStar) nbSubPats-2 else nbSubPats-1
-      def seqTree(binder: Symbol): Tree = if(firstIndexingBinder == 0) CODE.REF(binder) else pmgen.tupleSel(binder)(firstIndexingBinder+1)
-      def seqLenCmp                     = ts.last member nme.lengthCompare
-      val indexingIndices               = (0 to (lastIndexingBinder-firstIndexingBinder))
-      val nbIndexingIndices             = indexingIndices.length
+      def spliceApply(binder: Symbol): Tree = {
+        object splice extends Transformer {
+          override def transform(t: Tree) = t match {
+            case Apply(x, List(Ident(nme.SELECTOR_DUMMY))) =>
+              treeCopy.Apply(t, x, List(CODE.REF(binder)))
+            case _ => super.transform(t)
+          }
+        }
+        splice.transform(extractorCallIncludingDummy)
+      }
 
+      private lazy val rawSubPatTypes =
+        if (resultInMonad.typeSymbol eq UnitClass) Nil
+        else if(nbSubPats == 1)                    List(resultInMonad)
+        else getProductArgs(resultInMonad) match {
+          case Nil => List(resultInMonad)
+          case x   => x
+        }
 
-      // this error is checked by checkStarPatOK
-      // if(isSeq) assert(firstIndexingBinder + nbIndexingIndices + (if(lastIsStar) 1 else 0) == nbSubPats, "(typeInMonad, ts, subPatTypes, subPats)= "+(typeInMonad, ts, subPatTypes, subPats))
+      private def seqLenCmp                = rawSubPatTypes.last member nme.lengthCompare
+      private def seqTp                    = rawSubPatTypes.last baseType SeqClass
+      private lazy val firstIndexingBinder = rawSubPatTypes.length - 1 // rawSubPatTypes.last is the Seq, thus there are `rawSubPatTypes.length - 1` non-seq elements in the tuple
+      private lazy val lastIndexingBinder  = if(lastIsStar) nbSubPats-2 else nbSubPats-1
+      private lazy val expectedLength      = lastIndexingBinder - firstIndexingBinder + 1
+      private lazy val minLenToCheck       = if(lastIsStar) 1 else 0
+      private def seqTree(binder: Symbol)  = if(firstIndexingBinder == 0) CODE.REF(binder) else pmgen.tupleSel(binder)(firstIndexingBinder+1)
+
+      // the types for the binders corresponding to my subpatterns
+      // subPatTypes != args map (_.tpe) since the args may have more specific types than the constructor's parameter types
+      // replace last type (of shape Seq[A]) with RepeatedParam[A] so that formalTypes will
+      // repeat the last argument type to align the formals with the number of arguments
+      // require (nbSubPats > 0 && (!lastIsStar || isSeq))
+      def subPatTypes: List[Type] =
+        if(isSeq) {
+          val TypeRef(pre, SeqClass, args) = seqTp
+          // do repeated-parameter expansion to match up with the expected number of arguments (in casu, subpatterns)
+          formalTypes(rawSubPatTypes.init :+ typeRef(pre, RepeatedParamClass, args), nbSubPats)
+        } else rawSubPatTypes
+
+      // the trees that select the subpatterns on the extractor's result, referenced by `binder`
+      // require (nbSubPats > 0 && (!lastIsStar || isSeq))
+      def subPatRefs(binder: Symbol): List[Tree] = {
+        // only relevant if isSeq: (here to avoid capturing too much in the returned closure)
+        val indexingIndices               = (0 to (lastIndexingBinder-firstIndexingBinder))
+        val nbIndexingIndices             = indexingIndices.length
+
+        // this error is checked by checkStarPatOK
+        // if(isSeq) assert(firstIndexingBinder + nbIndexingIndices + (if(lastIsStar) 1 else 0) == nbSubPats, "(resultInMonad, ts, subPatTypes, subPats)= "+(resultInMonad, ts, subPatTypes, subPats))
 
-      def subPatRefs(binder: Symbol): List[Tree] =
         (if(isSeq) {
           // there are `firstIndexingBinder` non-seq tuple elements preceding the Seq
           ((1 to firstIndexingBinder) map pmgen.tupleSel(binder)) ++
@@ -549,27 +551,31 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
         }
         else if(nbSubPats == 1) List(CODE.REF(binder))
         else ((1 to nbSubPats) map pmgen.tupleSel(binder))).toList
-
-      // len may still be -1 even if isSeq
-      val len = if(!isSeq) -1 else lastIndexingBinder - firstIndexingBinder + 1
-      def unapplySeqLengthGuard(binder: Symbol, then: Tree) = { import CODE._
-        // the comparison to perform.  If the pivot is right ignoring, then a scrutinee sequence
-        // of >= pivot length could match it; otherwise it must be exactly equal.
-        def compareOp: (Tree, Tree) => Tree = if (lastIsStar) _ INT_>= _ else _ INT_== _
-
-        // scrutinee.lengthCompare(pivotLength) [== | >=] 0
-        def lenOk                        = compareOp( (seqTree(binder) DOT seqLenCmp)(LIT(len)), ZERO )
-
-        // wrapping in a null check on the scrutinee
-        // only check if minimal length is non-trivially satisfied
-        val minLenToCheck = if(lastIsStar) 1 else 0
-        if (len >= minLenToCheck) IF ((seqTree(binder) ANY_!= NULL) AND lenOk) THEN then ELSE pmgen.zero // treegen
-        else then
       }
 
-      (subPatTypes, subPatRefs, unapplySeqLengthGuard)
+      def lengthGuard(binder: Symbol, then: Tree) =
+        // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied
+        if (!isSeq || (expectedLength < minLenToCheck)) then
+        else { import CODE._
+          // `binder.lengthCompare(expectedLength)`
+          def checkExpectedLength = (seqTree(binder) DOT seqLenCmp)(LIT(expectedLength))
+
+          // the comparison to perform
+          // when the last subpattern is a wildcard-star the expectedLength is but a lower bound
+          // (otherwise equality is required)
+          def compareOp: (Tree, Tree) => Tree =
+            if (lastIsStar)  _ INT_>= _
+            else             _ INT_== _
+
+          // `if (binder != null && $checkExpectedLength [== | >=] 0) then else zero`
+          pmgen.condOpt((seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO), then)
+        }
+
+      override def toString() = extractorCall +": "+ extractorCall.tpe +" (symbol= "+ extractorCall.symbol +")."
     }
 
+
+
     /** 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.
@@ -603,7 +609,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
        // 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(REF(scrut), expectedTp.widen)
+        = pmgen._equals(REF(sym), scrut) AND pmgen._isInstanceOf(scrut, expectedTp.widen)
 
       expectedTp match {
           case SingleType(_, sym)                       => genEqualsAndInstanceOf(sym) // assert(sym.isStable) -- yep, this seems to be true, like always
@@ -612,7 +618,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
           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(REF(scrut), expectedTp))
+          case _                                        => maybeWithOuterCheck(scrut, expectedTp)(pmgen._isInstanceOf(scrut, expectedTp))
         }
     }
 
@@ -634,7 +640,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       // 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(REF(binder), expectedTp), outer)) OBJ_EQ expectedPrefix
+      (Select(pmgen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix
     }
 
     /** A conservative approximation of which patterns do not discern anything.
@@ -784,6 +790,10 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
     def matchingStrategy: Tree
     def matchingMonadType: Type
 
+    lazy val pmgen: CommonCodeGen with MatchingStrategyGen with MonadInstGen =
+      if (matchingMonadType.typeSymbol eq OptionClass) (new CommonCodeGen with MatchingStrategyGenOpt with MonadInstGenOpt {})
+      else (new CommonCodeGen with MatchingStrategyGen with MonadInstGen {})
+
     var ctr = 0
     def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x") = {ctr += 1;
       // assert(owner ne null)
@@ -797,16 +807,6 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
     def repackExistential(tp: Type): Type = if(tp == NoType) tp
       else existentialAbstraction((tp filter {t => t.typeSymbol.isExistentiallyBound}) map (_.typeSymbol), tp)
 
-    // object noShadowedUntyped extends Traverser {
-    //   override def traverse(t: Tree) {
-    //     if ((t.tpe ne null) && (t.tpe ne NoType)) okTree = t
-    //     else if(okTree ne null) println("untyped subtree "+ t +" in typed tree"+ okTree +" : "+ okTree.tpe)
-    //     super.traverse(t)
-    //   }
-    //   var okTree: Tree = null
-    // }
-    // private def c(t: Tree): Tree = noShadowedUntyped(t)
-
     object vpmName {
       val caseResult = "caseResult".toTermName
       val drop       = "drop".toTermName
@@ -834,26 +834,40 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       def drop(tgt: Tree)(n: Int): Tree               = (tgt DOT vpmName.drop) (LIT(n))
       def _equals(checker: Tree, binder: Symbol): Tree = checker MEMBER_== REF(binder)          // NOTE: checker must be the target of the ==, that's the patmat semantics for ya
       def and(a: Tree, b: Tree): Tree                 = a AND b
-      def _asInstanceOf(t: Tree, tp: Type): Tree       = gen.mkAsInstanceOf(t, repackExistential(tp), true, false)
-      def _isInstanceOf(t: Tree, tp: Type): Tree       = gen.mkIsInstanceOf(t, repackExistential(tp), true, false)
+      def _asInstanceOf(t: Tree, tp: Type): Tree      = gen.mkAsInstanceOf(t, repackExistential(tp), true, false)
+      def _asInstanceOf(b: Symbol, tp: Type): Tree    = gen.mkAsInstanceOf(REF(b), repackExistential(tp), true, false)
+      def _isInstanceOf(b: Symbol, tp: Type): Tree    = gen.mkIsInstanceOf(REF(b), repackExistential(tp), true, false)
+
+      def matchFromCases(scrut: Tree, scrutSym: Symbol, cases: List[Tree], pt: Type): Tree = {
+        // when specified, need to propagate pt explicitly, type inferencer can't handle it
+        val optPt = if(!isFullyDefined(pt)) NoType else appliedType(matchingMonadType, List(pt))
+        runOrElse(scrut, fun(scrutSym, cases reduceLeft typedOrElse(optPt)))
+      }
     }
 
     trait MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
       // methods in MatchingStrategy (the monad companion) -- used directly in translation
-      def runOrElse(scrut: Tree, matcher: Tree): Tree                    = ( (matchingStrategy DOT vpmName.runOrElse)(scrut) APPLY (matcher)        ) // matchingStrategy.runOrElse(scrut)(matcher)
-      def zero: Tree                                                     = ( matchingStrategy DOT vpmName.zero                                      ) // matchingStrategy.zero
-      def one(res: Tree, tp: Type = NoType, oneName: Name = vpmName.one): Tree = ( genTypeApply(matchingStrategy DOT oneName, tp) APPLY (res)         ) // matchingStrategy.one(res)
-      def caseResult(res: Tree, tp: Type = NoType): Tree                 = one(res, tp, vpmName.caseResult) // blow this one away for isDefinedAt
-      def or(f: Tree, as: List[Tree]): Tree                              = ( (matchingStrategy DOT vpmName.or)((f :: as): _*)                       ) // matchingStrategy.or(f, as)
-      def typedGuard(cond: Tree, expectedTp: Type, binder: Symbol): Tree = ( guard(cond, _asInstanceOf(REF(binder), expectedTp), expectedTp)        )
-      def cast(expectedTp: Type, binder: Symbol): Tree                   = ( typedGuard(_isInstanceOf(REF(binder), expectedTp), expectedTp, binder) )
-      def guard(t: Tree, then: Tree = UNIT, tp: Type = NoType): Tree     = ( genTypeApply((matchingStrategy DOT vpmName.guard), repackExistential(tp)) APPLY (t, then) ) // matchingStrategy.guard(t, then)
+      def runOrElse(scrut: Tree, matcher: Tree): Tree                    = (matchingStrategy DOT vpmName.runOrElse)(scrut) APPLY (matcher)  // matchingStrategy.runOrElse(scrut)(matcher)
+      def zero: Tree                                                     = matchingStrategy DOT vpmName.zero                                // matchingStrategy.zero
+      def one(res: Tree, tp: Type = NoType, oneName: Name = vpmName.one): Tree = genTypeApply(matchingStrategy DOT oneName, tp) APPLY (res) // matchingStrategy.one(res)
+      def or(f: Tree, as: List[Tree]): Tree                              = (matchingStrategy DOT vpmName.or)((f :: as): _*)                 // matchingStrategy.or(f, as)
+      def guard(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree     = genTypeApply((matchingStrategy DOT vpmName.guard), repackExistential(tp)) APPLY (c, then) // matchingStrategy.guard(c, then) -- a user-defined guard
+      def caseResult(res: Tree, tp: Type): Tree                          = (matchingStrategy DOT vpmName.caseResult) (pmgen._asInstanceOf(res, tp)) // matchingStrategy.caseResult(res), like one, but blow this one away for isDefinedAt (since it's the RHS of a case)
+
+      // TODO: get rid of the cast when it's unnecessary, but this requires type checking `body`
+      //       maybe this should be one of the optimisations we perform after generating the tree
+      // body.tpe is the type of the body after applying the substitution that represents the solution of GADT type inference
+      // need the explicit cast in case our substitutions in the body change the type to something that doesn't take GADT typing into account
+      def cond(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = genTypeApply((matchingStrategy DOT vpmName.guard), repackExistential(tp)) APPLY (c, then) // matchingStrategy.guard(c, then) -- an internal guard TODO: use different method call so exhaustiveness can distinguish it from user-defined guards
+      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)
     }
 
     trait MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
       // methods in the monad instance -- used directly in translation
-      def flatMap(a: Tree, b: Tree): Tree                                = ( (a DOT vpmName.flatMap)(b)                                             )
-      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree    = ( (genTyped(thisCase, pt) DOT vpmName.orElse)(genTyped(elseCase, pt))    )
+      def flatMap(a: Tree, b: Tree): Tree                                = (a DOT vpmName.flatMap)(b)
+      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree    = (genTyped(thisCase, pt) DOT vpmName.orElse)(genTyped(elseCase, pt))
     }
 
     // when we know we're targetting Option, do some inlining the optimizer won't do
@@ -861,7 +875,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(t: Tree, then: Tree = UNIT, tp: Type = NoType): Tree     = IF (t) THEN one(then, repackExistential(tp)) ELSE zero
+      override def guard(c: Tree, then: Tree = UNIT, tp: Type = NoType): Tree = condOpt(c, one(then, repackExistential(tp)))
     }
 
     trait MonadInstGenOpt extends MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
@@ -891,11 +905,17 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       }
     }
 
-    lazy val pmgen: CommonCodeGen with MatchingStrategyGen with MonadInstGen =
-      if (matchingMonadType.typeSymbol eq OptionClass) (new CommonCodeGen with MatchingStrategyGenOpt with MonadInstGenOpt {})
-      else (new CommonCodeGen with MatchingStrategyGen with MonadInstGen {})
-
     def genTypeApply(tfun: Tree, args: Type*): Tree                       = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
     def genTyped(t: Tree, tp: Type): Tree                                 = if(tp == NoType) t else Typed(t, TypeTree(repackExistential(tp)))
   }
 }
+
+// object noShadowedUntyped extends Traverser {
+//   override def traverse(t: Tree) {
+//     if ((t.tpe ne null) && (t.tpe ne NoType)) okTree = t
+//     else if(okTree ne null) println("untyped subtree "+ t +" in typed tree"+ okTree +" : "+ okTree.tpe)
+//     super.traverse(t)
+//   }
+//   var okTree: Tree = null
+// }
+// private def c(t: Tree): Tree = noShadowedUntyped(t)