Merge remote-tracking branch 'origin/2.10.x' into master

* origin/2.10.x:
  SI-7171 Consider prefix when assessing type finality.
  please ant with filenames, add comments
  Fixed error in reflection API docs about linearization order on method baseClasses
  Shadowed Implict typo (fixes no issue)
  remove unused imports

Conflicts:
	src/reflect/scala/reflect/internal/Types.scala

18 files changed, 307 insertions, 286 deletions

diff --git a/src/compiler/scala/tools/nsc/doc/html/page/Template.scala b/src/compiler/scala/tools/nsc/doc/html/page/Template.scala
index 0685f9ad70..c482134c4b 100644
--- a/src/compiler/scala/tools/nsc/doc/html/page/Template.scala
+++ b/src/compiler/scala/tools/nsc/doc/html/page/Template.scala
@@ -213,7 +213,7 @@ class Template(universe: doc.Universe, generator: DiagramGenerator, tpl: DocTemp
 
         { if (shadowedImplicitMembers.isEmpty) NodeSeq.Empty else
             <div id="values" class="values members">
-              <h3>Shadowed Implict Value Members</h3>
+              <h3>Shadowed Implicit Value Members</h3>
               <ol>{ shadowedImplicitMembers map (memberToHtml(_, tpl)) }</ol>
             </div>
         }
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
index 23c0272a30..9af4800a70 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala
@@ -6,26 +6,16 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
+import scala.tools.nsc.symtab._
 import scala.language.postfixOps
-import scala.tools.nsc.transform.TypingTransformers
-import scala.tools.nsc.transform.Transform
 import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
-import scala.reflect.internal.Types
+import scala.reflect.internal.util.Position
 import scala.reflect.internal.util.HashSet
 
 
-trait Logic { self: PatternMatching =>
+trait Logic extends Debugging  {
   import PatternMatchingStats._
-  val global: Global
-  import global.{Type, Tree, currentUnit, Position}
-
-  import debugging.patmatDebug
 
   private def max(xs: Seq[Int]) = if (xs isEmpty) 0 else xs max
   private def alignedColumns(cols: Seq[AnyRef]): Seq[String] = {
@@ -54,6 +44,9 @@ trait Logic { self: PatternMatching =>
   // http://users.encs.concordia.ca/~ta_ahmed/ms_thesis.pdf
   // propositional logic with constants and equality
   trait PropositionalLogic {
+    type Type
+    type Tree
+
     class Prop
     case class Eq(p: Var, q: Const) extends Prop
 
@@ -172,14 +165,11 @@ trait Logic { self: PatternMatching =>
       import scala.tools.cmd.FromString.IntFromString
       val max = sys.props.get("scalac.patmat.analysisBudget").collect(IntFromString.orElse{case "off" => Integer.MAX_VALUE}).getOrElse(256)
 
-      abstract class Exception extends RuntimeException("CNF budget exceeded") {
-        val advice: String
-        def warn(pos: Position, kind: String) = currentUnit.uncheckedWarning(pos, s"Cannot check match for $kind.\n$advice")
-      }
+      abstract class Exception(val advice: String) extends RuntimeException("CNF budget exceeded")
+
+      object exceeded extends Exception(
+          s"(The analysis required more space than allowed. Please try with scalac -Dscalac.patmat.analysisBudget=${AnalysisBudget.max*2} or -Dscalac.patmat.analysisBudget=off.)")
 
-      object exceeded extends Exception {
-        val advice = s"(The analysis required more space than allowed. Please try with scalac -Dscalac.patmat.analysisBudget=${AnalysisBudget.max*2} or -Dscalac.patmat.analysisBudget=off.)"
-      }
     }
 
     // convert finite domain propositional logic with subtyping to pure boolean propositional logic
@@ -229,7 +219,7 @@ trait Logic { self: PatternMatching =>
       val eqAxioms = formulaBuilder
       @inline def addAxiom(p: Prop) = addFormula(eqAxioms, eqFreePropToSolvable(p))
 
-      patmatDebug("removeVarEq vars: "+ vars)
+      debug.patmat("removeVarEq vars: "+ vars)
       vars.foreach { v =>
         // if v.domainSyms.isEmpty, we must consider the domain to be infinite
         // otherwise, since the domain fully partitions the type of the value,
@@ -253,8 +243,8 @@ trait Logic { self: PatternMatching =>
         }
       }
 
-      patmatDebug("eqAxioms:\n"+ cnfString(toFormula(eqAxioms)))
-      patmatDebug("pure:"+ pure.map(p => cnfString(p)).mkString("\n"))
+      debug.patmat("eqAxioms:\n"+ cnfString(toFormula(eqAxioms)))
+      debug.patmat("pure:"+ pure.map(p => cnfString(p)).mkString("\n"))
 
       if (Statistics.canEnable) Statistics.stopTimer(patmatAnaVarEq, start)
 
@@ -402,7 +392,7 @@ trait Logic { self: PatternMatching =>
       //
       if (Statistics.canEnable) patmatCNFSizes(res.size).value += 1
 
-//      patmatDebug("cnf for\n"+ p +"\nis:\n"+cnfString(res))
+//      debug.patmat("cnf for\n"+ p +"\nis:\n"+cnfString(res))
       res
     }
   }
@@ -430,19 +420,19 @@ trait Logic { self: PatternMatching =>
     // returns all solutions, if any (TODO: better infinite recursion backstop -- detect fixpoint??)
     def findAllModelsFor(f: Formula): List[Model] = {
       val vars: Set[Sym] = f.flatMap(_ collect {case l: Lit => l.sym}).toSet
-      // patmatDebug("vars "+ vars)
+      // debug.patmat("vars "+ vars)
       // the negation of a model -(S1=True/False /\ ... /\ SN=True/False) = clause(S1=False/True, ...., SN=False/True)
       def negateModel(m: Model) = clause(m.toSeq.map{ case (sym, pos) => Lit(sym, !pos) } : _*)
 
       def findAllModels(f: Formula, models: List[Model], recursionDepthAllowed: Int = 10): List[Model]=
         if (recursionDepthAllowed == 0) models
         else {
-          patmatDebug("find all models for\n"+ cnfString(f))
+          debug.patmat("find all models for\n"+ cnfString(f))
           val model = findModelFor(f)
           // if we found a solution, conjunct the formula with the model's negation and recurse
           if (model ne NoModel) {
             val unassigned = (vars -- model.keySet).toList
-            patmatDebug("unassigned "+ unassigned +" in "+ model)
+            debug.patmat("unassigned "+ unassigned +" in "+ model)
             def force(lit: Lit) = {
               val model = withLit(findModelFor(dropUnit(f, lit)), lit)
               if (model ne NoModel) List(model)
@@ -451,7 +441,7 @@ trait Logic { self: PatternMatching =>
             val forced = unassigned flatMap { s =>
               force(Lit(s, true)) ++ force(Lit(s, false))
             }
-            patmatDebug("forced "+ forced)
+            debug.patmat("forced "+ forced)
             val negated = negateModel(model)
             findAllModels(f :+ negated, model :: (forced ++ models), recursionDepthAllowed - 1)
           }
@@ -479,7 +469,7 @@ trait Logic { self: PatternMatching =>
     def findModelFor(f: Formula): Model = {
       @inline def orElse(a: Model, b: => Model) = if (a ne NoModel) a else b
 
-      patmatDebug("DPLL\n"+ cnfString(f))
+      debug.patmat("DPLL\n"+ cnfString(f))
 
       val start = if (Statistics.canEnable) Statistics.startTimer(patmatAnaDPLL) else null
 
@@ -489,7 +479,7 @@ trait Logic { self: PatternMatching =>
         else f.find(_.size == 1) match {
           case Some(unitClause) =>
             val unitLit = unitClause.head
-            // patmatDebug("unit: "+ unitLit)
+            // debug.patmat("unit: "+ unitLit)
             withLit(findModelFor(dropUnit(f, unitLit)), unitLit)
           case _ =>
             // partition symbols according to whether they appear in positive and/or negative literals
@@ -509,12 +499,12 @@ trait Logic { self: PatternMatching =>
               // (since equality on literals is in terms of equality
               //  of the underlying symbol and its positivity, simply construct a new Lit)
               val pureLit = Lit(pureSym, pos(pureSym))
-              // patmatDebug("pure: "+ pureLit +" pures: "+ pures +" impures: "+ impures)
+              // debug.patmat("pure: "+ pureLit +" pures: "+ pures +" impures: "+ impures)
               val simplified = f.filterNot(_.contains(pureLit))
               withLit(findModelFor(simplified), pureLit)
             } else {
               val split = f.head.head
-              // patmatDebug("split: "+ split)
+              // debug.patmat("split: "+ split)
               orElse(findModelFor(f :+ clause(split)), findModelFor(f :+ clause(-split)))
             }
         }
@@ -524,8 +514,13 @@ trait Logic { self: PatternMatching =>
         satisfiableWithModel
     }
   }
+}
 
+trait ScalaLogic extends Logic { self: PatternMatching =>
   trait TreesAndTypesDomain extends PropositionalLogic with CheckableTreeAndTypeAnalysis {
+    type Type = global.Type
+    type Tree = global.Tree
+
     // resets hash consing -- only supposed to be called by TreeMakersToProps
     def prepareNewAnalysis(): Unit = { Var.resetUniques(); Const.resetUniques() }
 
@@ -542,7 +537,7 @@ trait Logic { self: PatternMatching =>
       private[this] val id: Int = Var.nextId
 
       // private[this] var canModify: Option[Array[StackTraceElement]] = None
-      private[this] def ensureCanModify() = {} //if (canModify.nonEmpty) patmatDebug("BUG!"+ this +" modified after having been observed: "+ canModify.get.mkString("\n"))
+      private[this] def ensureCanModify() = {} //if (canModify.nonEmpty) debug.patmat("BUG!"+ this +" modified after having been observed: "+ canModify.get.mkString("\n"))
 
       private[this] def observed() = {} //canModify = Some(Thread.currentThread.getStackTrace)
 
@@ -613,8 +608,8 @@ trait Logic { self: PatternMatching =>
             (lower != NullConst && !upper.isValue &&
              instanceOfTpImplies(if (lower.isValue) lower.wideTp else lower.tp, upper.tp))
 
-          // if(r) patmatDebug("implies    : "+(lower, lower.tp, upper, upper.tp))
-          // else  patmatDebug("NOT implies: "+(lower, upper))
+          // if(r) debug.patmat("implies    : "+(lower, lower.tp, upper, upper.tp))
+          // else  debug.patmat("NOT implies: "+(lower, upper))
 
 
         /** does V = C preclude V having value `other`?
@@ -630,8 +625,8 @@ trait Logic { self: PatternMatching =>
         def excludes(a: Const, b: Const): Boolean =
           a != b && ((a == NullConst || b == NullConst) || (a.isValue && b.isValue))
 
-          // if(r) patmatDebug("excludes    : "+(a, a.tp, b, b.tp))
-          // else  patmatDebug("NOT excludes: "+(a, b))
+          // if(r) debug.patmat("excludes    : "+(a, a.tp, b, b.tp))
+          // else  debug.patmat("NOT excludes: "+(a, b))
 
 /*
 [ HALF BAKED FANCINESS: //!equalitySyms.exists(common => implies(common.const, a) && implies(common.const, b)))
@@ -678,9 +673,9 @@ trait Logic { self: PatternMatching =>
           val (excluded, notExcluded) = todo partition (b => excludes(sym.const, b.const))
           val implied = notExcluded filter (b => implies(sym.const, b.const))
 
-          patmatDebug("eq axioms for: "+ sym.const)
-          patmatDebug("excluded: "+ excluded)
-          patmatDebug("implied: "+ implied)
+          debug.patmat("eq axioms for: "+ sym.const)
+          debug.patmat("excluded: "+ excluded)
+          debug.patmat("implied: "+ implied)
 
           excluded foreach { excludedSym => excludedPair += ExcludedPair(sym.const, excludedSym.const)}
 
@@ -729,11 +724,11 @@ trait Logic { self: PatternMatching =>
         uniques.get(tp).getOrElse(
           uniques.find {case (oldTp, oldC) => oldTp =:= tp} match {
             case Some((_, c)) =>
-              patmatDebug("unique const: "+ (tp, c))
+              debug.patmat("unique const: "+ (tp, c))
               c
             case _ =>
               val fresh = mkFresh
-              patmatDebug("uniqued const: "+ (tp, fresh))
+              debug.patmat("uniqued const: "+ (tp, fresh))
               uniques(tp) = fresh
               fresh
           })
@@ -749,12 +744,12 @@ trait Logic { self: PatternMatching =>
         if (!t.symbol.isStable) t.tpe.narrow
         else trees find (a => a.correspondsStructure(t)(sameValue)) match {
           case Some(orig) =>
-            patmatDebug("unique tp for tree: "+ (orig, orig.tpe))
+            debug.patmat("unique tp for tree: "+ (orig, orig.tpe))
             orig.tpe
           case _ =>
             // duplicate, don't mutate old tree (TODO: use a map tree -> type instead?)
             val treeWithNarrowedType = t.duplicate setType t.tpe.narrow
-            patmatDebug("uniqued: "+ (t, t.tpe, treeWithNarrowedType.tpe))
+            debug.patmat("uniqued: "+ (t, t.tpe, treeWithNarrowedType.tpe))
             trees += treeWithNarrowedType
             treeWithNarrowedType.tpe
         }
@@ -839,7 +834,7 @@ trait Logic { self: PatternMatching =>
       }
     }
     sealed class ValueConst(val tp: Type, val wideTp: Type, override val toString: String) extends Const {
-      // patmatDebug("VC"+(tp, wideTp, toString))
+      // debug.patmat("VC"+(tp, wideTp, toString))
       assert(!(tp =:= NullTp)) // TODO: assert(!tp.isStable)
       /*private[this] val id: Int = */Const.nextValueId
       def isValue = true
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala
index 1e12975880..ed990105fd 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala
@@ -6,21 +6,12 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
 import scala.language.postfixOps
-import scala.tools.nsc.transform.TypingTransformers
-import scala.tools.nsc.transform.Transform
 import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
-import scala.reflect.internal.Types
-import scala.reflect.internal.util.HashSet
+import scala.reflect.internal.util.Position
 
 trait TreeAndTypeAnalysis extends Debugging {
-  val global: Global
   import global.{Tree, Type, Symbol, definitions, analyzer,
     ConstantType, Literal, Constant,  appliedType, WildcardType, TypeRef, ModuleClassSymbol,
     nestedMemberType, TypeMap, Ident}
@@ -28,7 +19,6 @@ trait TreeAndTypeAnalysis extends Debugging {
   import definitions._
   import analyzer.Typer
 
-  import debugging.patmatDebug
 
   // we use subtyping as a model for implication between instanceof tests
   // i.e., when S <:< T we assume x.isInstanceOf[S] implies x.isInstanceOf[T]
@@ -70,7 +60,7 @@ trait TreeAndTypeAnalysis extends Debugging {
           Some(List(tp))
         // make sure it's not a primitive, else (5: Byte) match { case 5 => ... } sees no Byte
         case sym if !sym.isSealed || isPrimitiveValueClass(sym) =>
-          patmatDebug("enum unsealed "+ (tp, sym, sym.isSealed, isPrimitiveValueClass(sym)))
+          debug.patmat("enum unsealed "+ (tp, sym, sym.isSealed, isPrimitiveValueClass(sym)))
           None
         case sym =>
           val subclasses = (
@@ -78,7 +68,7 @@ trait TreeAndTypeAnalysis extends Debugging {
             // symbols which are both sealed and abstract need not be covered themselves, because
             // all of their children must be and they cannot otherwise be created.
             filterNot (x => x.isSealed && x.isAbstractClass && !isPrimitiveValueClass(x)))
-          patmatDebug("enum sealed -- subclasses: "+ (sym, subclasses))
+          debug.patmat("enum sealed -- subclasses: "+ (sym, subclasses))
 
           val tpApprox = typer.infer.approximateAbstracts(tp)
           val pre = tpApprox.prefix
@@ -92,11 +82,11 @@ trait TreeAndTypeAnalysis extends Debugging {
               val memberType  = nestedMemberType(sym, pre, tpApprox.typeSymbol.owner)
               val subTp       = appliedType(memberType, sym.typeParams.map(_ => WildcardType))
               val subTpApprox = typer.infer.approximateAbstracts(subTp) // TODO: needed?
-              // patmatDebug("subtp"+(subTpApprox <:< tpApprox, subTpApprox, tpApprox))
+              // debug.patmat("subtp"+(subTpApprox <:< tpApprox, subTpApprox, tpApprox))
               if (subTpApprox <:< tpApprox) Some(checkableType(subTp))
               else None
             })
-          patmatDebug("enum sealed "+ (tp, tpApprox) + " as "+ validSubTypes)
+          debug.patmat("enum sealed "+ (tp, tpApprox) + " as "+ validSubTypes)
           Some(validSubTypes)
       }
 
@@ -118,7 +108,7 @@ trait TreeAndTypeAnalysis extends Debugging {
       }
 
       val res = typeArgsToWildcardsExceptArray(tp)
-      patmatDebug("checkable "+(tp, res))
+      debug.patmat("checkable "+(tp, res))
       res
     }
 
@@ -129,16 +119,15 @@ trait TreeAndTypeAnalysis extends Debugging {
       val checkable = (
            (isTupleType(tp) && tupleComponents(tp).exists(tp => !uncheckableType(tp)))
         || enumerateSubtypes(tp).nonEmpty)
-      // if (!checkable) patmatDebug("deemed uncheckable: "+ tp)
+      // if (!checkable) debug.patmat("deemed uncheckable: "+ tp)
       !checkable
     }
   }
 }
 
-trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
+trait MatchAnalysis extends TreeAndTypeAnalysis { self: PatternMatching =>
   import PatternMatchingStats._
-  val global: Global
-  import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition,
+  import global.{Tree, Type, Symbol, CaseDef, atPos,
     Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest,
     ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser,
     Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef,
@@ -148,8 +137,6 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
   import definitions._
   import analyzer.{Typer, ErrorUtils, formalTypes}
 
-  import debugging.patmatDebug
-
   /**
    * Represent a match as a formula in propositional logic that encodes whether the match matches (abstractly: we only consider types)
    *
@@ -196,8 +183,8 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
         uniqueTypeProps getOrElseUpdate((testedPath, pt), Eq(Var(testedPath), TypeConst(checkableType(pt))))
 
       // 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)
-      private val pointsToBound = scala.collection.mutable.HashSet(root)
-      private val trees         = scala.collection.mutable.HashSet.empty[Tree]
+      private val pointsToBound = mutable.HashSet(root)
+      private val trees         = mutable.HashSet.empty[Tree]
 
       // the substitution that renames variables to variables in pointsToBound
       private var normalize: Substitution  = EmptySubstitution
@@ -215,7 +202,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
       def unique(t: Tree, tpOverride: Type = NoType): Tree =
         trees find (a => a.correspondsStructure(t)(sameValue)) match {
           case Some(orig) =>
-            // patmatDebug("unique: "+ (t eq orig, orig))
+            // debug.patmat("unique: "+ (t eq orig, orig))
             orig
           case _ =>
             trees += t
@@ -253,14 +240,14 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
           // reverse substitution that would otherwise replace a variable we already encountered by a new variable
           // NOTE: this forgets the more precise type we have for these later variables, but that's probably okay
           normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_)))
-          // patmatDebug ("normalize subst: "+ normalize)
+          // debug.patmat ("normalize subst: "+ normalize)
 
           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
-          // patmatDebug("pointsToBound: "+ pointsToBound)
+          // debug.patmat("pointsToBound: "+ pointsToBound)
 
           accumSubst >>= okSubst
-          // patmatDebug("accumSubst: "+ accumSubst)
+          // debug.patmat("accumSubst: "+ accumSubst)
         }
 
         def handleUnknown(tm: TreeMaker): Prop
@@ -351,18 +338,21 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
       /\(tests.takeWhile(t => !t.treeMaker.isInstanceOf[BodyTreeMaker]).map(t => t.prop))
 
     def showTreeMakers(cases: List[List[TreeMaker]]) = {
-      patmatDebug("treeMakers:")
-      patmatDebug(alignAcrossRows(cases, ">>"))
+      debug.patmat("treeMakers:")
+      debug.patmat(alignAcrossRows(cases, ">>"))
     }
 
     def showTests(testss: List[List[Test]]) = {
-      patmatDebug("tests: ")
-      patmatDebug(alignAcrossRows(testss, "&"))
+      debug.patmat("tests: ")
+      debug.patmat(alignAcrossRows(testss, "&"))
     }
   }
 
   trait SymbolicMatchAnalysis extends TreeMakerApproximation  { self: CodegenCore =>
-    // TODO: model dependencies between variables: if V1 corresponds to (x: List[_]) and V2 is (x.hd), V2 cannot be assigned when V1 = null or V1 = Nil
+    def uncheckedWarning(pos: Position, msg: String) = global.currentUnit.uncheckedWarning(pos, msg)
+    def warn(pos: Position, ex: AnalysisBudget.Exception, kind: String) = uncheckedWarning(pos, s"Cannot check match for $kind.\n${ex.advice}")
+
+  // TODO: model dependencies between variables: if V1 corresponds to (x: List[_]) and V2 is (x.hd), V2 cannot be assigned when V1 = null or V1 = Nil
     // right now hackily implement this by pruning counter-examples
     // unreachability would also benefit from a more faithful representation
 
@@ -403,8 +393,8 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
         var reachable  = true
         var caseIndex  = 0
 
-        patmatDebug("reachability, vars:\n"+ ((propsCasesFail flatMap gatherVariables).distinct map (_.describe) mkString ("\n")))
-        patmatDebug("equality axioms:\n"+ cnfString(eqAxiomsOk))
+        debug.patmat("reachability, vars:\n"+ ((propsCasesFail flatMap gatherVariables).distinct map (_.describe) mkString ("\n")))
+        debug.patmat("equality axioms:\n"+ cnfString(eqAxiomsOk))
 
         // invariant (prefixRest.length == current.length) && (prefix.reverse ++ prefixRest == symbolicCasesFail)
         // termination: prefixRest.length decreases by 1
@@ -418,8 +408,8 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
             current = current.tail
             val model = findModelFor(andFormula(current.head, toFormula(prefix)))
 
-            // patmatDebug("trying to reach:\n"+ cnfString(current.head) +"\nunder prefix:\n"+ cnfString(prefix))
-            // if (NoModel ne model) patmatDebug("reached: "+ modelString(model))
+            // debug.patmat("trying to reach:\n"+ cnfString(current.head) +"\nunder prefix:\n"+ cnfString(prefix))
+            // if (NoModel ne model) debug.patmat("reached: "+ modelString(model))
 
             reachable = NoModel ne model
           }
@@ -430,7 +420,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
         if (reachable) None else Some(caseIndex)
       } catch {
         case ex: AnalysisBudget.Exception =>
-          ex.warn(prevBinder.pos, "unreachability")
+          warn(prevBinder.pos, ex, "unreachability")
           None // CNF budget exceeded
       }
     }
@@ -451,7 +441,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
       val symbolicCases = approx.approximateMatch(cases, approx.onUnknown { tm =>
         approx.fullRewrite.applyOrElse[TreeMaker, Prop](tm, {
           case BodyTreeMaker(_, _) => True // irrelevant -- will be discarded by symbolCase later
-          case _ => // patmatDebug("backing off due to "+ tm)
+          case _ => // debug.patmat("backing off due to "+ tm)
             backoff = true
             False
         })
@@ -474,11 +464,11 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
         val matchFails = Not(\/(symbolicCases))
 
   // debug output:
-        patmatDebug("analysing:")
+        debug.patmat("analysing:")
         showTreeMakers(cases)
 
-        // patmatDebug("\nvars:\n"+ (vars map (_.describe) mkString ("\n")))
-        // patmatDebug("\nmatchFails as CNF:\n"+ cnfString(propToSolvable(matchFails)))
+        // debug.patmat("\nvars:\n"+ (vars map (_.describe) mkString ("\n")))
+        // debug.patmat("\nmatchFails as CNF:\n"+ cnfString(propToSolvable(matchFails)))
 
         try {
           // find the models (under which the match fails)
@@ -493,7 +483,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
           pruned
         } catch {
           case ex : AnalysisBudget.Exception =>
-            ex.warn(prevBinder.pos, "exhaustivity")
+            warn(prevBinder.pos, ex, "exhaustivity")
             Nil // CNF budget exceeded
         }
       }
@@ -580,14 +570,14 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
       // ...
       val varAssignment = modelToVarAssignment(model)
 
-      patmatDebug("var assignment for model "+ model +":\n"+ varAssignmentString(varAssignment))
+      debug.patmat("var assignment for model "+ model +":\n"+ varAssignmentString(varAssignment))
 
       // chop a path into a list of symbols
       def chop(path: Tree): List[Symbol] = path match {
         case Ident(_) => List(path.symbol)
         case Select(pre, name) => chop(pre) :+ path.symbol
         case _ =>
-          // patmatDebug("don't know how to chop "+ path)
+          // debug.patmat("don't know how to chop "+ path)
           Nil
       }
 
@@ -647,7 +637,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
         def toCounterExample(beBrief: Boolean = false): CounterExample =
           if (!allFieldAssignmentsLegal) NoExample
           else {
-            patmatDebug("describing "+ (variable, equalTo, notEqualTo, fields, cls, allFieldAssignmentsLegal))
+            debug.patmat("describing "+ (variable, equalTo, notEqualTo, fields, cls, allFieldAssignmentsLegal))
             val res = prunedEqualTo match {
               // a definite assignment to a value
               case List(eq: ValueConst) if fields.isEmpty => ValueExample(eq)
@@ -688,7 +678,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching =>
               // TODO: improve reasoning -- in the mean time, a false negative is better than an annoying false positive
               case _ => NoExample
             }
-            patmatDebug("described as: "+ res)
+            debug.patmat("described as: "+ res)
             res
           }
 
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala
index a22d35a6b4..ce19d9cba8 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala
@@ -6,30 +6,23 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
+import scala.tools.nsc.symtab.Flags.SYNTHETIC
 import scala.language.postfixOps
-import scala.tools.nsc.transform.TypingTransformers
-import scala.tools.nsc.transform.Transform
-import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
-import scala.reflect.internal.Types
-import scala.reflect.internal.util.HashSet
+import scala.reflect.internal.util.Position
+import scala.reflect.internal.util.NoPosition
 
-trait CodeGen { self: PatternMatching =>
+/** Factory methods used by TreeMakers to make the actual trees.
+ *
+ * We have two modes in which to emit trees: optimized (the default)
+ * and pure (aka "virtualized": match is parametric in its monad).
+ */
+trait MatchCodeGen { self: PatternMatching =>
   import PatternMatchingStats._
-  val global: Global
-  import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition,
-    Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest,
-    ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser,
-    Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef,
-    UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol,
-    nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName}
+  import global.{nme, treeInfo, definitions, gen, Tree, Type, Symbol, NoSymbol,
+    appliedType, NoType, MethodType, newTermName, Name,
+    Block, Literal, Constant, EmptyTree, Function, Typed, ValDef, LabelDef}
   import definitions._
-//  import analyzer.{Typer, ErrorUtils, formalTypes}
 
   ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   // generate actual trees
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala
index 1419d0cb93..c14b4ebc3b 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala
@@ -6,33 +6,28 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
+import scala.tools.nsc.symtab.Flags.MUTABLE
 import scala.language.postfixOps
-import scala.tools.nsc.transform.TypingTransformers
-import scala.tools.nsc.transform.Transform
 import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
-import scala.reflect.internal.Types
-import scala.reflect.internal.util.HashSet
+import scala.reflect.internal.util.Position
+import scala.reflect.internal.util.NoPosition
 
-trait Optimization { self: PatternMatching =>
+/** Optimize and analyze matches based on their TreeMaker-representation.
+ *
+ * The patmat translation doesn't rely on this, so it could be disabled in principle.
+ *
+ * TODO: split out match analysis
+ */
+trait MatchOptimization { self: PatternMatching =>
   import PatternMatchingStats._
-  val global: Global
-  import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition,
-    Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest,
-    ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser,
-    Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef,
-    UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol,
-    nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName}
+  import global.{Tree, Type, Symbol, NoSymbol, CaseDef, atPos,
+    ConstantType, Literal, Constant, gen, EmptyTree,
+    Typed, treeInfo, nme, Ident,
+    Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw}
 
-  import definitions._
-  import analyzer.{Typer, ErrorUtils, formalTypes}
+  import global.definitions._
 
-  import debugging.patmatDebug
 
   ////
   trait CommonSubconditionElimination extends TreeMakerApproximation { self: OptimizedCodegen =>
@@ -44,7 +39,7 @@ trait Optimization { self: PatternMatching =>
      * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree)
      */
     def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
-      patmatDebug("before CSE:")
+      debug.patmat("before CSE:")
       showTreeMakers(cases)
 
       val testss = approximateMatchConservative(prevBinder, cases)
@@ -94,7 +89,7 @@ trait Optimization { self: PatternMatching =>
         tested.clear()
         tests dropWhile storeDependencies
       }
-      patmatDebug("dependencies: "+ dependencies)
+      debug.patmat("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
@@ -128,8 +123,8 @@ trait Optimization { self: PatternMatching =>
               case _ =>
             }
 
-            patmatDebug("sharedPrefix: "+ sharedPrefix)
-            patmatDebug("suffix: "+ sharedPrefix)
+            debug.patmat("sharedPrefix: "+ sharedPrefix)
+            debug.patmat("suffix: "+ sharedPrefix)
             // if the shared prefix contains interesting conditions (!= True)
             // and the last of such interesting shared conditions reuses another treemaker's test
             // replace the whole sharedPrefix by a ReusingCondTreeMaker
@@ -145,7 +140,7 @@ trait Optimization { self: PatternMatching =>
       // replace original treemakers that are reused (as determined when computing collapsed),
       // by ReusedCondTreeMakers
       val reusedMakers = collapsed mapConserve (_ mapConserve reusedOrOrig)
-      patmatDebug("after CSE:")
+      debug.patmat("after CSE:")
       showTreeMakers(reusedMakers)
       reusedMakers
     }
@@ -460,7 +455,7 @@ trait Optimization { self: PatternMatching =>
                   CaseDef(Alternative(switchableAlts), guard, body)
                 }
               case _ =>
-                // patmatDebug("can't emit switch for "+ makers)
+                // debug.patmat("can't emit switch for "+ makers)
                 None //failure (can't translate pattern to a switch)
             }
           }
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala
index d03e3741ef..82f13d9777 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala
@@ -6,32 +6,26 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
 import scala.language.postfixOps
-import scala.tools.nsc.transform.TypingTransformers
-import scala.tools.nsc.transform.Transform
 import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
-import scala.reflect.internal.Types
-import scala.reflect.internal.util.HashSet
 
-trait Translation { self: PatternMatching  =>
+/** Translate typed Trees that represent pattern matches into the patternmatching IR, defined by TreeMakers.
+ */
+trait MatchTranslation { self: PatternMatching  =>
   import PatternMatchingStats._
-  val global: Global
-  import global._
-
-  import definitions._
-  import analyzer.{Typer, ErrorUtils, formalTypes}
-
-  import debugging.patmatDebug
-
-
-  trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore =>
-    import typer.{typed, context, silent, reallyExists}
+  import global.{phase, currentRun, Symbol,
+    Apply, Bind, CaseDef, ClassInfoType, Ident, Literal, Match,
+    Alternative, Constant, EmptyTree, Select, Star, This, Throw, Typed, UnApply,
+    Type, MethodType, WildcardType, PolyType, ErrorType, NoType, TypeRef, typeRef,
+    Name, NoSymbol, Position, Tree, atPos, glb, rootMirror, treeInfo, nme, Transformer,
+    elimAnonymousClass, asCompactDebugString, hasLength, devWarning}
+  import global.definitions.{ThrowableClass, SeqClass, ScalaPackageClass, BooleanClass, UnitClass, RepeatedParamClass,
+    repeatedToSeq, isRepeatedParamType, getProductArgs}
+  import global.analyzer.{ErrorUtils, formalTypes}
+
+  trait MatchTranslator extends MatchMonadInterface { self: TreeMakers with CodegenCore =>
+    import typer.context
 
     // Why is it so difficult to say "here's a name and a context, give me any
     // matching symbol in scope" ? I am sure this code is wrong, but attempts to
@@ -133,7 +127,7 @@ trait Translation { self: PatternMatching  =>
       if (phase.id >= currentRun.uncurryPhase.id)
         devWarning(s"running translateMatch past uncurry (at $phase) on $selector match $cases")
 
-      patmatDebug("translating "+ cases.mkString("{", "\n", "}"))
+      debug.patmat("translating "+ cases.mkString("{", "\n", "}"))
 
       val start = if (Statistics.canEnable) Statistics.startTimer(patmatNanos) else null
 
@@ -249,14 +243,14 @@ trait Translation { self: PatternMatching  =>
         if (!extractor.isTyped) ErrorUtils.issueNormalTypeError(patTree, "Could not typecheck extractor call: "+ extractor)(context)
         // if (extractor.resultInMonad == ErrorType) throw new TypeError(pos, "Unsupported extractor type: "+ extractor.tpe)
 
-        patmatDebug("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType))
+        debug.patmat("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType))
 
         // must use type `tp`, which is provided by extractor's result, not the type expected by binder,
         // as b.info may be based on a Typed type ascription, which has not been taken into account yet by the translation
         // (it will later result in a type test when `tp` is not a subtype of `b.info`)
         // TODO: can we simplify this, together with the Bound case?
         (extractor.subPatBinders, extractor.subPatTypes).zipped foreach { case (b, tp) =>
-          patmatDebug("changing "+ b +" : "+ b.info +" -> "+ tp)
+          debug.patmat("changing "+ b +" : "+ b.info +" -> "+ tp)
           b setInfo tp
         }
 
@@ -312,7 +306,7 @@ trait Translation { self: PatternMatching  =>
         case WildcardPattern() => noFurtherSubPats()
         case UnApply(unfun, args) =>
           // TODO: check unargs == args
-          // patmatDebug("unfun: "+ (unfun.tpe, unfun.symbol.ownerChain, unfun.symbol.info, patBinder.info))
+          // debug.patmat("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.
@@ -379,7 +373,7 @@ trait Translation { self: PatternMatching  =>
       */
 
         case Bind(n, p) => // this happens in certain ill-formed programs, there'll be an error later
-          patmatDebug("WARNING: Bind tree with unbound symbol "+ patTree)
+          debug.patmat("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(_) | ArrayValue  => error("stone age pattern relics encountered!")
@@ -536,8 +530,8 @@ trait Translation { self: PatternMatching  =>
       // private val orig            = fun match {case tpt: TypeTree => tpt.original case _ => fun}
       // private val origExtractorTp = unapplyMember(orig.symbol.filter(sym => reallyExists(unapplyMember(sym.tpe))).tpe).tpe
       // private val extractorTp     = if (wellKinded(fun.tpe)) fun.tpe else existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType)
-      // patmatDebug("ExtractorCallProd: "+ (fun.tpe, existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType)))
-      // patmatDebug("ExtractorCallProd: "+ (fun.tpe, args map (_.tpe)))
+      // debug.patmat("ExtractorCallProd: "+ (fun.tpe, existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType)))
+      // debug.patmat("ExtractorCallProd: "+ (fun.tpe, args map (_.tpe)))
       private def constructorTp = fun.tpe
 
       def isTyped    = fun.isTyped
@@ -677,59 +671,4 @@ trait Translation { self: PatternMatching  =>
       }
     }
   }
-
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-// substitution
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-  trait TypedSubstitution extends MatchMonadInterface {
-    object Substitution {
-      def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
-      // requires sameLength(from, to)
-      def apply(from: List[Symbol], to: List[Tree]) =
-        if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
-    }
-
-    class Substitution(val from: List[Symbol], val to: List[Tree]) {
-      // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
-      // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
-      def apply(tree: Tree): Tree = {
-        // according to -Ystatistics 10% of translateMatch's time is spent in this method...
-        // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
-        if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
-        else (new Transformer {
-          private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
-            if (origTp == null || origTp == NoType) to
-            // important: only type when actually substing and when original tree was typed
-            // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
-            else typer.typed(to)
-
-          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.setPos(tree.pos), tree.tpe)
-              else subst(from.tail, to.tail)
-
-            tree match {
-              case Ident(_) => subst(from, to)
-              case _        => super.transform(tree)
-            }
-          }
-        }).transform(tree)
-      }
-
-
-      // the substitution that chains `other` before `this` substitution
-      // forall t: Tree. this(other(t)) == (this >> other)(t)
-      def >>(other: Substitution): Substitution = {
-        val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) =>  !other.from.contains(f) }
-        new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
-      }
-      override def toString = (from.map(_.name) zip to) mkString("Substitution(", ", ", ")")
-    }
-
-    object EmptySubstitution extends Substitution(Nil, Nil) {
-      override def apply(tree: Tree): Tree = tree
-      override def >>(other: Substitution): Substitution = other
-    }
-  }
-}
\ No newline at end of file
+}
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMaking.scala
index b334a6b228..c9285f9229 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMaking.scala
@@ -6,33 +6,26 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
+import scala.tools.nsc.symtab.Flags.{SYNTHETIC, ARTIFACT}
 import scala.language.postfixOps
-import scala.tools.nsc.transform.TypingTransformers
-import scala.tools.nsc.transform.Transform
 import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
-import scala.reflect.internal.Types
-import scala.reflect.internal.util.HashSet
+import scala.reflect.internal.util.Position
+import scala.reflect.internal.util.NoPosition
 
-trait TreeMaking { self: PatternMatching =>
+/** Translate our IR (TreeMakers) into actual Scala Trees using the factory methods in MatchCodeGen.
+ *
+ * The IR is mostly concerned with sequencing, substitution, and rendering all necessary conditions,
+ * mostly agnostic to whether we're in optimized/pure (virtualized) mode.
+ */
+trait MatchTreeMaking { self: PatternMatching =>
   import PatternMatchingStats._
-  val global: Global
-  import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition, settings,
-    Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest,
-    ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser,
-    Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef,
-    UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol,
-    nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName}
-
-  import definitions._
-  import analyzer.{Typer, ErrorUtils, formalTypes}
+  import global.{Tree, Type, Symbol, CaseDef, atPos, settings,
+    Select, Block, ThisType, SingleType, NoPrefix, NoType, needsOuterTest,
+    ConstantType, Literal, Constant, gen, This, EmptyTree, map2, NoSymbol, Traverser,
+    Function, Typed, treeInfo, TypeRef, DefTree}
 
-  import debugging.patmatDebug
+  import global.definitions.{SomeClass, AnyRefClass, UncheckedClass, BooleanClass}
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // the making of the trees
@@ -62,7 +55,7 @@ trait TreeMaking { self: PatternMatching =>
 
       private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
         if (currSub ne null) {
-          patmatDebug("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst))
+          debug.patmat("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst))
           Thread.dumpStack()
         }
         else currSub = outerSubst >> substitution
@@ -172,7 +165,7 @@ trait TreeMaking { self: PatternMatching =>
         if (!emitVars) in
         else {
           // binders in `subPatBindersStored` that are referenced by tree `in`
-          val usedBinders = new collection.mutable.HashSet[Symbol]()
+          val usedBinders = new mutable.HashSet[Symbol]()
           // all potentially stored subpat binders
           val potentiallyStoredBinders = stored.unzip._1.toSet
           // compute intersection of all symbols in the tree `in` and all potentially stored subpat binders
@@ -391,7 +384,7 @@ trait TreeMaking { self: PatternMatching =>
     **/
     case class TypeTestTreeMaker(prevBinder: Symbol, testedBinder: Symbol, expectedTp: Type, nextBinderTp: Type)(override val pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker {
       import TypeTestTreeMaker._
-      patmatDebug("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp))
+      debug.patmat("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp))
 
       lazy val outerTestNeeded = (
           !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
@@ -527,7 +520,7 @@ trait TreeMaking { self: PatternMatching =>
     def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree =
       fixerUpper(owner, scrut.pos){
         def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree)))
-        patmatDebug("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}")))
+        debug.patmat("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}")))
 
         val (unchecked, requireSwitch) =
           if (settings.XnoPatmatAnalysis.value) (true, false)
@@ -581,27 +574,27 @@ trait TreeMaking { self: PatternMatching =>
         t match {
           case Function(_, _) if t.symbol == NoSymbol =>
             t.symbol = currentOwner.newAnonymousFunctionValue(t.pos)
-            patmatDebug("new symbol for "+ (t, t.symbol.ownerChain))
+            debug.patmat("new symbol for "+ (t, t.symbol.ownerChain))
           case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) =>
-            patmatDebug("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain))
+            debug.patmat("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain))
             t.symbol.owner = currentOwner
           case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2)
-            patmatDebug("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain))
+            debug.patmat("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain))
             if(d.symbol.moduleClass ne NoSymbol)
               d.symbol.moduleClass.owner = currentOwner
 
             d.symbol.owner = currentOwner
           // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) =>
-          patmatDebug("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain))
+          debug.patmat("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain))
           case _ =>
         }
         super.traverse(t)
       }
 
       // override def apply
-      // patmatDebug("before fixerupper: "+ xTree)
+      // debug.patmat("before fixerupper: "+ xTree)
       // currentRun.trackerFactory.snapshot()
-      // patmatDebug("after fixerupper")
+      // debug.patmat("after fixerupper")
       // currentRun.trackerFactory.snapshot()
     }
   }
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala
index 49f13c07d4..38d148c915 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala
@@ -6,23 +6,19 @@
 
 package scala.tools.nsc.transform.patmat
 
-import scala.tools.nsc.{ast, symtab, typechecker, transform, Global}
-import transform._
-import typechecker._
-import symtab._
-import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT}
+import scala.tools.nsc.Global
+import scala.tools.nsc.ast
 import scala.language.postfixOps
 import scala.tools.nsc.transform.TypingTransformers
 import scala.tools.nsc.transform.Transform
-import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
 import scala.reflect.internal.Types
-import scala.reflect.internal.util.HashSet
+import scala.reflect.internal.util.Position
 
 /** Translate pattern matching.
   *
-  * Either into optimized if/then/else's,
-  * or virtualized as method calls (these methods form a zero-plus monad), similar in spirit to how for-comprehensions are compiled.
+  * Either into optimized if/then/else's, or virtualized as method calls (these methods form a zero-plus monad),
+  * similar in spirit to how for-comprehensions are compiled.
   *
   * For each case, express all patterns as extractor calls, guards as 0-ary extractors, and sequence them using `flatMap`
   * (lifting the body of the case into the monad using `one`).
@@ -41,15 +37,12 @@ import scala.reflect.internal.util.HashSet
 trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
                       with Debugging
                       with Interface
-                      with Translation
-                      with TreeMaking
-                      with CodeGen
-                      with Logic
-                      with Analysis
-                      with Optimization {
-
-  import PatternMatchingStats._
-  val global: Global
+                      with MatchTranslation
+                      with MatchTreeMaking
+                      with MatchCodeGen
+                      with ScalaLogic
+                      with MatchAnalysis
+                      with MatchOptimization {
   import global._
 
   val phaseName: String = "patmat"
@@ -75,29 +68,32 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       case _ => super.transform(tree)
     }
 
-    def translator: MatchTranslation with CodegenCore = {
+    // TODO: only instantiate new match translator when localTyper has changed
+    // override def atOwner[A](tree: Tree, owner: Symbol)(trans: => A): A
+    // as this is the only time TypingTransformer changes it
+    def translator: MatchTranslator with CodegenCore = {
       new OptimizingMatchTranslator(localTyper)
     }
   }
 
-  class PureMatchTranslator(val typer: analyzer.Typer, val matchStrategy: Tree) extends MatchTranslation with TreeMakers with PureCodegen
-  class OptimizingMatchTranslator(val typer: analyzer.Typer)                    extends MatchTranslation with TreeMakers with MatchOptimizations
+  class PureMatchTranslator(val typer: analyzer.Typer, val matchStrategy: Tree) extends MatchTranslator with TreeMakers with PureCodegen
+  class OptimizingMatchTranslator(val typer: analyzer.Typer)                    extends MatchTranslator with TreeMakers with MatchOptimizations
 }
 
-trait Debugging {
+trait HasGlobal {
   val global: Global
-  import global.settings
+}
 
-  // TODO: the inliner fails to inline the closures to patmatDebug
-  object debugging {
-    val printPatmat = settings.Ypatmatdebug.value
-    @inline final def patmatDebug(s: => String) = if (printPatmat) println(s)
+trait Debugging extends HasGlobal {
+  // TODO: the inliner fails to inline the closures to debug.patmat unless the method is nested in an object
+  object debug {
+    val printPatmat = global.settings.Ypatmatdebug.value
+    @inline final def patmat(s: => String) = if (printPatmat) println(s)
   }
 }
 
-trait Interface { self: ast.TreeDSL =>
-  val global: Global
-  import global.{newTermName, Position, Type, analyzer, ErrorType, Symbol, Tree}
+trait Interface { self: ast.TreeDSL with HasGlobal =>
+  import global.{newTermName, analyzer, Type, ErrorType, Symbol, Tree}
   import analyzer.Typer
 
   // 2.10/2.11 compatibility
@@ -180,6 +176,64 @@ trait Interface { self: ast.TreeDSL =>
 
     protected def matchMonadSym: Symbol
   }
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// substitution
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  trait TypedSubstitution extends MatchMonadInterface {
+    object Substitution {
+      def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
+      // requires sameLength(from, to)
+      def apply(from: List[Symbol], to: List[Tree]) =
+        if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
+    }
+
+    class Substitution(val from: List[Symbol], val to: List[Tree]) {
+      import global.{Transformer, Ident, NoType}
+
+      // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
+      // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
+      def apply(tree: Tree): Tree = {
+        // according to -Ystatistics 10% of translateMatch's time is spent in this method...
+        // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
+        if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
+        else (new Transformer {
+          private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
+            if (origTp == null || origTp == NoType) to
+            // important: only type when actually substing and when original tree was typed
+            // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
+            else typer.typed(to)
+
+          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.setPos(tree.pos), tree.tpe)
+              else subst(from.tail, to.tail)
+
+            tree match {
+              case Ident(_) => subst(from, to)
+              case _        => super.transform(tree)
+            }
+          }
+        }).transform(tree)
+      }
+
+
+      // the substitution that chains `other` before `this` substitution
+      // forall t: Tree. this(other(t)) == (this >> other)(t)
+      def >>(other: Substitution): Substitution = {
+        val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) =>  !other.from.contains(f) }
+        new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
+      }
+      override def toString = (from.map(_.name) zip to) mkString("Substitution(", ", ", ")")
+    }
+
+    object EmptySubstitution extends Substitution(Nil, Nil) {
+      override def apply(tree: Tree): Tree = tree
+      override def >>(other: Substitution): Substitution = other
+    }
+  }
 }
 
 object PatternMatchingStats {
diff --git a/src/reflect/scala/reflect/api/Symbols.scala b/src/reflect/scala/reflect/api/Symbols.scala
index a4a4277239..dbad3dd478 100644
--- a/src/reflect/scala/reflect/api/Symbols.scala
+++ b/src/reflect/scala/reflect/api/Symbols.scala
@@ -946,7 +946,7 @@ trait Symbols { self: Universe =>
     def knownDirectSubclasses: Set[Symbol]
 
     /** The list of all base classes of this type (including its own typeSymbol)
-     *  in reverse linearization order, starting with the class itself and ending
+     *  in linearization order, starting with the class itself and ending
      *  in class Any.
      *
      *  @group Class
diff --git a/src/reflect/scala/reflect/api/Types.scala b/src/reflect/scala/reflect/api/Types.scala
index e8e9e9c048..e5140f23e5 100644
--- a/src/reflect/scala/reflect/api/Types.scala
+++ b/src/reflect/scala/reflect/api/Types.scala
@@ -144,7 +144,7 @@ trait Types extends ImplicitTags {
     def =:= (that: Type): Boolean
 
     /** The list of all base classes of this type (including its own typeSymbol)
-     *  in reverse linearization order, starting with the class itself and ending
+     *  in linearization order, starting with the class itself and ending
      *  in class Any.
      */
     def baseClasses: List[Symbol]
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index ce7fae8628..5cb6f78874 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -372,7 +372,7 @@ trait Types extends api.Types { self: SymbolTable =>
      *  This is assessed to be the case if the class is final,
      *  and all type parameters (if any) are invariant.
      */
-    def isFinalType = typeSymbol.hasOnlyBottomSubclasses
+    def isFinalType = typeSymbol.hasOnlyBottomSubclasses && prefix.isStable
 
     /** Is this type completed (i.e. not a lazy type)? */
     def isComplete: Boolean = true
diff --git a/test/files/neg/t7171.check b/test/files/neg/t7171.check
new file mode 100644
index 0000000000..ecd768afda
--- /dev/null
+++ b/test/files/neg/t7171.check
@@ -0,0 +1,6 @@
+t7171.scala:2: warning: The outer reference in this type test cannot be checked at run time.
+  final case class A()
+                   ^
+error: No warnings can be incurred under -Xfatal-warnings.
+one warning found
+one error found
diff --git a/test/files/neg/t7171.flags b/test/files/neg/t7171.flags
new file mode 100644
index 0000000000..464cc20ea6
--- /dev/null
+++ b/test/files/neg/t7171.flags
@@ -0,0 +1 @@
+-Xfatal-warnings -unchecked
\ No newline at end of file
diff --git a/test/files/neg/t7171.scala b/test/files/neg/t7171.scala
new file mode 100644
index 0000000000..534b2070a3
--- /dev/null
+++ b/test/files/neg/t7171.scala
@@ -0,0 +1,11 @@
+trait T {
+  final case class A()
+
+  // Was:
+  // error: scrutinee is incompatible with pattern type;
+  // found   : T.this.A
+  // required: T#A
+  def foo(a: T#A) = a match {
+    case _: A => true; case _ => false
+  }
+}
diff --git a/test/files/neg/t7171b.check b/test/files/neg/t7171b.check
new file mode 100644
index 0000000000..bf695afea7
--- /dev/null
+++ b/test/files/neg/t7171b.check
@@ -0,0 +1,6 @@
+t7171b.scala:2: warning: The outer reference in this type test cannot be checked at run time.
+  final case class A()
+                   ^
+error: No warnings can be incurred under -Xfatal-warnings.
+one warning found
+one error found
diff --git a/test/files/neg/t7171b.flags b/test/files/neg/t7171b.flags
new file mode 100644
index 0000000000..464cc20ea6
--- /dev/null
+++ b/test/files/neg/t7171b.flags
@@ -0,0 +1 @@
+-Xfatal-warnings -unchecked
\ No newline at end of file
diff --git a/test/files/neg/t7171b.scala b/test/files/neg/t7171b.scala
new file mode 100644
index 0000000000..53c7787f8b
--- /dev/null
+++ b/test/files/neg/t7171b.scala
@@ -0,0 +1,15 @@
+trait T {
+  final case class A()
+}
+
+final class U extends T {
+  // this match should also not be deemed impossible
+  def foo(a: U#A) = a match {
+    case _: A => true; case _ => false
+  }
+
+  // this match should also not be deemed impossible
+  def bar(a: T#A) = a match {
+    case _: A => true; case _ => false
+  }
+}
diff --git a/test/files/run/t7171.scala b/test/files/run/t7171.scala
new file mode 100644
index 0000000000..97585b9860
--- /dev/null
+++ b/test/files/run/t7171.scala
@@ -0,0 +1,22 @@
+trait T {
+  final case class A()
+
+  // Was:
+  // error: scrutinee is incompatible with pattern type;
+  // found   : T.this.A
+  // required: T#A
+  def foo(a: T#A) = a match {
+    case _: A => true; case _ => false
+  }
+}
+
+object Test extends App {
+  val t1 = new T {}
+  val t2 = new T {}
+  val a1 = new t1.A()
+  val a2 = new t1.A()
+  assert(t1.foo(a1))
+  // as noted in the unchecked warning (tested in the corresponding neg test),
+  // the outer pointer isn't checked
+  assert(t1.foo(a2))
+}