remove unused imports

7 files changed, 206 insertions, 263 deletions

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..39157e3843 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,7 +119,7 @@ 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
     }
   }
@@ -137,8 +127,7 @@ trait TreeAndTypeAnalysis extends Debugging {
 
 trait Analysis 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..4c024cf71c 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala
@@ -6,30 +6,18 @@
 
 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 =>
   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..eda30b88b7 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala
@@ -6,33 +6,22 @@
 
 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 =>
   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 +33,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 +83,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 +117,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 +134,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 +449,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..984d82d955 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala
@@ -6,32 +6,24 @@
 
 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  =>
   import PatternMatchingStats._
-  val global: Global
-  import global._
-
-  import definitions._
-  import analyzer.{Typer, ErrorUtils, formalTypes}
-
-  import debugging.patmatDebug
-
+  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}
+  import global.definitions.{ThrowableClass, SeqClass, ScalaPackageClass, BooleanClass, UnitClass, RepeatedParamClass,
+    repeatedToSeq, isRepeatedParamType, getProductArgs}
+  import global.analyzer.{ErrorUtils, formalTypes}
 
   trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore =>
-    import typer.{typed, context, silent, reallyExists}
+    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 +125,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 +241,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 +304,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 +371,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 +528,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
@@ -678,58 +670,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/MatchTreeMakers.scala
index b334a6b228..da9d6b3531 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala
@@ -6,33 +6,25 @@
 
 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.{ast, symtab, typechecker, transform, Global}
+//import transform._
+//import typechecker._
+//import symtab._
+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 =>
   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 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 definitions._
-  import analyzer.{Typer, ErrorUtils, formalTypes}
-
-  import debugging.patmatDebug
+  import global.definitions.{SomeClass, AnyRefClass, UncheckedClass, BooleanClass}
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // the making of the trees
@@ -62,7 +54,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 +164,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 +383,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 +519,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 +573,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 26078118fd..03c4e78771 100644
--- a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala
+++ b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala
@@ -6,18 +6,14 @@
 
 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.
   *
@@ -44,12 +40,9 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
                       with Translation
                       with TreeMaking
                       with CodeGen
-                      with Logic
+                      with ScalaLogic
                       with Analysis
                       with Optimization {
-
-  import PatternMatchingStats._
-  val global: Global
   import global._
 
   val phaseName: String = "patmat"
@@ -86,20 +79,20 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
   class OptimizingMatchTranslator(val typer: analyzer.Typer)                    extends MatchTranslation 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
@@ -183,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 {