SI-6011 switches: unreachability, guard-free form

A complete overhaul. The original implementation in SI-5830 (#821) was pretty buggy.

[from the doc comment of `collapseGuardedCases`:]

Collapse guarded cases that switch on the same constant (the last case may be unguarded).

Cases with patterns A and B switch on the same constant iff for all values x that match A also match B and vice versa.
(This roughly corresponds to equality on trees modulo alpha renaming and reordering of alternatives.)

The rewrite only applies if some of the cases are guarded (this must be checked before invoking this method).

The rewrite goes through the switch top-down and merges each case with the subsequent cases it is implied by
(i.e. it matches if they match, not taking guards into account)

If there are no unreachable cases, all cases can be uniquely assigned to a partition of such 'overlapping' cases,
save for the default case (thus we jump to it rather than copying it several times).
(The cases in a partition are implied by the principal element of the partition.)

The overlapping cases are merged into one case with their guards pushed into the body as follows
(with P the principal element of the overlapping patterns Pi):

   `{case Pi if(G_i) => B_i }*` is rewritten to `case P => {if(G_i) B_i}*`

The rewrite fails (and returns Nil) when:
  (1) there is a subsequence of overlapping cases that has an unguarded case in the middle;
      only the last case of each subsequence of overlapping cases may be unguarded (this is implied by unreachability)

  (2) there are overlapping cases that differ (tested by `caseImpliedBy`)
      cases with patterns A and B are overlapping if for SOME value x, A matches x implies B matches y OR vice versa  <-- note the difference with case equality defined above
      for example `case 'a' | 'b' =>` and `case 'b' =>` are different and overlapping (overlapping and equality disregard guards)

Improved by @retronym's feedback in the following ways:
  - fix patternEquals (it's now quadratic, but correct)
  - update neg/t6011 to test the improved patternEquals
  - remove side-effect-in-condition ugliness
  - introduce isGuardedCase
  - docs & various code clarity

Also closes SI-6048 (duplicate).

11 files changed, 319 insertions, 143 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
index b1e68e2757..da45b9bde3 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
@@ -27,14 +27,13 @@ import reflect.internal.util.Statistics
   * Cases are combined into a pattern match using the `orElse` combinator (the implicit failure case is expressed using the monad's `zero`).
   *
   * TODO:
-  *  - use TypeTags for type testing
   *  - DCE (on irrefutable patterns)
   *  - update spec and double check it's implemented correctly (see TODO's)
   *
   * (longer-term) TODO:
   *  - user-defined unapplyProd
   *  - recover GADT typing by locally inserting implicit witnesses to type equalities derived from the current case, and considering these witnesses during subtyping (?)
-  *  - recover exhaustivity and unreachability checking using a variation on the type-safe builder pattern
+  *  - recover exhaustivity/unreachability of user-defined extractors by partitioning the types they match on using an HList or similar type-level structure
   */
 trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL {   // self: Analyzer =>
   import Statistics._
@@ -1248,6 +1247,24 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 
     def typesConform(tp: Type, pt: Type) = ((tp eq pt) || (tp <:< pt))
 
+    // 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]
+    // unfortunately this is not true in general:
+    // SI-6022 expects instanceOfTpImplies(ProductClass.tpe, AnyRefClass.tpe)
+    def instanceOfTpImplies(tp: Type, tpImplied: Type) = {
+      val tpValue    = tp.typeSymbol.isPrimitiveValueClass
+
+      // pretend we're comparing to Any when we're actually comparing to AnyVal or AnyRef
+      // (and the subtype is respectively a value type or not a value type)
+      // this allows us to reuse subtyping as a model for implication between instanceOf tests
+      // the latter don't see a difference between AnyRef, Object or Any when comparing non-value types -- SI-6022
+      val tpImpliedNormalizedToAny =
+        if (tpImplied =:= (if (tpValue) AnyValClass.tpe else AnyRefClass.tpe)) AnyClass.tpe
+        else tpImplied
+
+      tp <:< tpImpliedNormalizedToAny
+    }
+
     abstract class CommonCodegen extends AbsCodegen { import CODE._
       def fun(arg: Symbol, body: Tree): Tree           = Function(List(ValDef(arg)), body)
       def genTypeApply(tfun: Tree, args: Type*): Tree  = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
@@ -2173,25 +2190,6 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 
       def isAny = wideTp.typeSymbol == AnyClass
 
-      // 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]
-      // unfortunately this is not true in general:
-      // SI-6022 expects instanceOfTpImplies(ProductClass.tpe, AnyRefClass.tpe)
-      private def instanceOfTpImplies(tp: Type, tpImplied: Type) = {
-        val tpValue    = tp.typeSymbol.isPrimitiveValueClass
-
-        // pretend we're comparing to Any when we're actually comparing to AnyVal or AnyRef
-        // (and the subtype is respectively a value type or not a value type)
-        // this allows us to reuse subtyping as a model for implication between instanceOf tests
-        // the latter don't see a difference between AnyRef, Object or Any when comparing non-value types -- SI-6022
-        val tpImpliedNormalizedToAny =
-          if ((tpValue && tpImplied =:= AnyValClass.tpe) ||
-              (!tpValue && tpImplied =:= AnyRefClass.tpe)) AnyClass.tpe
-          else tpImplied
-
-        tp <:< tpImpliedNormalizedToAny
-      }
-
       final def implies(other: Const): Boolean = {
         val r = (this, other) match {
           case (_: ValueConst, _: ValueConst) => this == other // hashconsed
@@ -2942,6 +2940,8 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 
   //// SWITCHES -- TODO: operate on Tests rather than TreeMakers
   trait SwitchEmission extends TreeMakers with OptimizedMatchMonadInterface { self: CodegenCore =>
+    import treeInfo.isGuardedCase
+
     abstract class SwitchMaker {
       abstract class SwitchableTreeMakerExtractor { def unapply(x: TreeMaker): Option[Tree] }
       val SwitchableTreeMaker: SwitchableTreeMakerExtractor
@@ -2978,91 +2978,170 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
 
       /** Collapse guarded cases that switch on the same constant (the last case may be unguarded).
        *
-       * `{case C if(G_i) => B_i | case C'_j if G'_j => B'_j}*`  is rewritten to
-       * `case C => {if(G_i) B_i}*` ++ rewrite({case C'_j if G'_j => B'_j}*)
+       * Cases with patterns A and B switch on the same constant iff for all values x that match A also match B and vice versa.
+       * (This roughly corresponds to equality on trees modulo alpha renaming and reordering of alternatives.)
+       *
+       * The rewrite only applies if some of the cases are guarded (this must be checked before invoking this method).
+       *
+       * The rewrite goes through the switch top-down and merges each case with the subsequent cases it is implied by
+       * (i.e. it matches if they match, not taking guards into account)
+       *
+       * If there are no unreachable cases, all cases can be uniquely assigned to a partition of such 'overlapping' cases,
+       * save for the default case (thus we jump to it rather than copying it several times).
+       * (The cases in a partition are implied by the principal element of the partition.)
        *
+       * The overlapping cases are merged into one case with their guards pushed into the body as follows
+       * (with P the principal element of the overlapping patterns Pi):
+       *
+       *    `{case Pi if(G_i) => B_i }*` is rewritten to `case P => {if(G_i) B_i}*`
+       *
+       * The rewrite fails (and returns Nil) when:
+       *   (1) there is a subsequence of overlapping cases that has an unguarded case in the middle;
+       *       only the last case of each subsequence of overlapping cases may be unguarded (this is implied by unreachability)
+       *
+       *   (2) there are overlapping cases that differ (tested by `caseImpliedBy`)
+       *       cases with patterns A and B are overlapping if for SOME value x, A matches x implies B matches y OR vice versa  <-- note the difference with case equality defined above
+       *       for example `case 'a' | 'b' =>` and `case 'b' =>` are different and overlapping (overlapping and equality disregard guards)
+       *
+       * The second component of the returned tuple indicates whether we'll need to emit a labeldef to jump to the default case.
        */
-      private def collapseGuardedCases(cases: List[CaseDef]) = {
-        // requires(switchesOnSameConst.forall(caseChecksSameConst(switchesOnSameConst.head)))
-        def collapse(switchesOnSameConst: List[CaseDef]): List[CaseDef] =
-          if (switchesOnSameConst.tail.isEmpty && (switchesOnSameConst.head.guard == EmptyTree)) switchesOnSameConst
-          else {
-            val commonPattern = switchesOnSameConst.head.pat
-
-            // jump to default case (either the user-supplied one or the synthetic one)
-            // unless we're collapsing the default case, then re-use the same body as the synthetic catchall (throwing a matcherror, rethrowing the exception)
-            val jumpToDefault: Tree =
-              if (!canJump || isDefault(CaseDef(commonPattern, EmptyTree, EmptyTree))) defaultBody
-              else Apply(Ident(defaultLabel), Nil)
-
-            val guardedBody = switchesOnSameConst.foldRight(jumpToDefault){
-              // the last case may be un-guarded (we know it's the last one since fold's accum == jumpToDefault)
-              // --> replace jumpToDefault by the un-guarded case's body
-              case (CaseDef(_, EmptyTree, b), `jumpToDefault`)  => b
-              case (CaseDef(_, g, b), els) if g != EmptyTree => If(g, b, els)
-              // error: the un-guarded case did not come last
-              case _ =>
-                return switchesOnSameConst
-            }
+      private def collapseGuardedCases(cases: List[CaseDef]): (List[CaseDef], Boolean) = {
+        // requires(same.forall(caseEquals(same.head)))
+        // requires(same.nonEmpty, same)
+        def collapse(same: List[CaseDef], isDefault: Boolean): CaseDef = {
+          val commonPattern = same.head.pat
+          // jump to default case (either the user-supplied one or the synthetic one)
+          // unless we're collapsing the default case: then we re-use the same body as the synthetic catchall (throwing a matcherror, rethrowing the exception)
+          val jumpToDefault: Tree =
+            if (isDefault || !canJump) defaultBody
+            else Apply(Ident(defaultLabel), Nil)
+
+          val guardedBody = same.foldRight(jumpToDefault){
+            // the last case may be un-guarded (we know it's the last one since fold's accum == jumpToDefault)
+            // --> replace jumpToDefault by the un-guarded case's body
+            case (CaseDef(_, EmptyTree, b), `jumpToDefault`)     => b
+            case (cd@CaseDef(_, g, b), els) if isGuardedCase(cd) => If(g, b, els)
+          }
 
-            // if the cases that we're going to collapse bind variables,
-            // must replace them by the single binder introduced by the collapsed case
-            val binders = switchesOnSameConst.collect{case CaseDef(x@Bind(_, _), _, _) if x.symbol != NoSymbol => x.symbol}
-            val (pat, guardedBodySubst) =
-              if (binders.isEmpty) (commonPattern, guardedBody)
-              else {
-                // create a single fresh binder to subsume the old binders (and their types)
-                // TODO: I don't think the binder's types can actually be different (due to checks in caseChecksSameConst)
-                // if they do somehow manage to diverge, the lub might not be precise enough and we could get a type error
-                val binder = freshSym(binders.head.pos, lub(binders.map(_.tpe)))
-
-                // the patterns in switchesOnSameConst are equal (according to caseChecksSameConst) and modulo variable-binding
-                // we can thus safely pick the first one arbitrarily, provided we correct binding
-                val origPatWithoutBind = commonPattern match {
-                  case Bind(b, orig) => orig
-                  case o => o
-                }
-                // need to replace `defaultSym` as well -- it's used in `defaultBody` (see `jumpToDefault` above)
-                val unifiedBody = guardedBody.substituteSymbols(defaultSym :: binders, binder :: binders.map(_ => binder))
-                (Bind(binder, origPatWithoutBind), unifiedBody)
+          // if the cases that we're going to collapse bind variables,
+          // must replace them by the single binder introduced by the collapsed case
+          val binders = same.collect{case CaseDef(x@Bind(_, _), _, _) if x.symbol != NoSymbol => x.symbol}
+          val (pat, guardedBodySubst) =
+            if (binders.isEmpty) (commonPattern, guardedBody)
+            else {
+              // create a single fresh binder to subsume the old binders (and their types)
+              // TODO: I don't think the binder's types can actually be different (due to checks in caseEquals)
+              // if they do somehow manage to diverge, the lub might not be precise enough and we could get a type error
+              // TODO: reuse name exactly if there's only one binder in binders
+              val binder = freshSym(binders.head.pos, lub(binders.map(_.tpe)), binders.head.name.toString)
+
+              // the patterns in same are equal (according to caseEquals)
+              // we can thus safely pick the first one arbitrarily, provided we correct binding
+              val origPatWithoutBind = commonPattern match {
+                case Bind(b, orig) => orig
+                case o => o
               }
+              // need to replace `defaultSym` as well -- it's used in `defaultBody` (see `jumpToDefault` above)
+              val unifiedBody = guardedBody.substituteSymbols(defaultSym :: binders, binder :: binders.map(_ => binder))
+              (Bind(binder, origPatWithoutBind), unifiedBody)
+            }
 
-            List(CaseDef(pat, EmptyTree, guardedBodySubst))
-          }
+          atPos(commonPattern.pos)(CaseDef(pat, EmptyTree, guardedBodySubst))
+        }
 
-        @annotation.tailrec def partitionAndCollapse(cases: List[CaseDef], accum: List[CaseDef] = Nil): List[CaseDef] =
-          if (cases.isEmpty) accum
-          else {
-            val (same, others) = cases.tail partition (caseChecksSameConst(cases.head))
-            partitionAndCollapse(others, accum ++ collapse(cases.head :: same))
+        // requires cases.exists(isGuardedCase) (otherwise the rewrite is pointless)
+        var remainingCases = cases
+        val collapsed      = collection.mutable.ListBuffer.empty[CaseDef]
+
+        // when some of collapsed cases (except for the default case itself) did not include an un-guarded case
+        // we'll need to emit a labeldef for the default case
+        var needDefault  = false
+
+        while (remainingCases.nonEmpty) {
+          val currCase              = remainingCases.head
+          val currIsDefault         = isDefault(CaseDef(currCase.pat, EmptyTree, EmptyTree))
+          val (impliesCurr, others) =
+            // the default case is implied by all cases, no need to partition (and remainingCases better all be default cases as well)
+            if (currIsDefault) (remainingCases.tail, Nil)
+            else remainingCases.tail partition (caseImplies(currCase))
+
+          val unguardedComesLastOrAbsent =
+            (!isGuardedCase(currCase) && impliesCurr.isEmpty) || { val LastImpliesCurr = impliesCurr.length - 1
+            impliesCurr.indexWhere(oc => !isGuardedCase(oc)) match {
+              // if all cases are guarded we will have to jump to the default case in the final else
+              // (except if we're collapsing the default case itself)
+              case -1 =>
+                if (!currIsDefault) needDefault = true
+                true
+
+              // last case is not guarded, no need to jump to the default here
+              // note: must come after case -1 => (since LastImpliesCurr may be -1)
+              case LastImpliesCurr => true
+
+              case _ => false
+            }}
+
+          if (unguardedComesLastOrAbsent /*(1)*/ && impliesCurr.forall(caseEquals(currCase)) /*(2)*/) {
+            collapsed += (
+              if (impliesCurr.isEmpty && !isGuardedCase(currCase)) currCase
+              else collapse(currCase :: impliesCurr, currIsDefault)
+            )
+
+            remainingCases = others
+          } else { // fail
+            collapsed.clear()
+            remainingCases = Nil
           }
+        }
 
-        // common case: no rewrite needed when there are no guards
-        if (cases.forall(c => c.guard == EmptyTree)) cases
-        else partitionAndCollapse(cases)
+        (collapsed.toList, needDefault)
       }
 
-      private def caseChecksSameConst(x: CaseDef)(y: CaseDef) = (x, y) match {
+      private def caseEquals(x: CaseDef)(y: CaseDef) = patternEquals(x.pat)(y.pat)
+      private def patternEquals(x: Tree)(y: Tree): Boolean = (x, y) match {
+        case (Alternative(xs), Alternative(ys)) =>
+          xs.forall(x => ys.exists(patternEquals(x))) &&
+          ys.forall(y => xs.exists(patternEquals(y)))
+        case (Alternative(pats), _) => pats.forall(p => patternEquals(p)(y))
+        case (_, Alternative(pats)) => pats.forall(q => patternEquals(x)(q))
         // regular switch
-        case (CaseDef(Literal(Constant(cx)), _, _), CaseDef(Literal(Constant(cy)), _, _)) => cx == cy
-        case (CaseDef(Ident(nme.WILDCARD), _, _), CaseDef(Ident(nme.WILDCARD), _, _)) => true
+        case (Literal(Constant(cx)), Literal(Constant(cy))) => cx == cy
+        case (Ident(nme.WILDCARD), Ident(nme.WILDCARD))     => true
         // type-switch for catch
-        case (CaseDef(Bind(_, Typed(Ident(nme.WILDCARD), tpX)), _, _), CaseDef(Bind(_, Typed(Ident(nme.WILDCARD), tpY)), _, _)) => tpX.tpe =:= tpY.tpe
+        case (Bind(_, Typed(Ident(nme.WILDCARD), tpX)), Bind(_, Typed(Ident(nme.WILDCARD), tpY))) => tpX.tpe =:= tpY.tpe
         case _ => false
       }
 
-      private def checkNoGuards(cs: List[CaseDef]) =
-        if (cs.exists{case CaseDef(_, g, _) => g != EmptyTree case _ => false}) None
-        else Some(cs)
+      // if y matches then x matches for sure (thus, if x comes before y, y is unreachable)
+      private def caseImplies(x: CaseDef)(y: CaseDef) = patternImplies(x.pat)(y.pat)
+      private def patternImplies(x: Tree)(y: Tree): Boolean = (x, y) match {
+        // since alternatives are flattened, must treat them as separate cases
+        case (Alternative(pats), _) => pats.exists(p => patternImplies(p)(y))
+        case (_, Alternative(pats)) => pats.exists(q => patternImplies(x)(q))
+        // regular switch
+        case (Literal(Constant(cx)), Literal(Constant(cy))) => cx == cy
+        case (Ident(nme.WILDCARD), _)                       => true
+        // type-switch for catch
+        case (Bind(_, Typed(Ident(nme.WILDCARD), tpX)),
+              Bind(_, Typed(Ident(nme.WILDCARD), tpY)))     => instanceOfTpImplies(tpY.tpe, tpX.tpe)
+        case _ => false
+      }
+
+      private def noGuards(cs: List[CaseDef]): Boolean = !cs.exists(isGuardedCase)
 
-      // requires(cs.forall(_.guard == EmptyTree))
+      // must do this before removing guards from cases and collapsing (SI-6011, SI-6048)
       private def unreachableCase(cs: List[CaseDef]): Option[CaseDef] = {
         var cases = cs
         var unreachable: Option[CaseDef] = None
 
         while (cases.nonEmpty && unreachable.isEmpty) {
-          if (isDefault(cases.head) && cases.tail.nonEmpty) unreachable = Some(cases.tail.head)
-          else unreachable = cases.tail.find(caseChecksSameConst(cases.head))
+          val currCase = cases.head
+          if (isDefault(currCase) && cases.tail.nonEmpty) // subsumed by the `else if` that follows, but faster
+            unreachable = Some(cases.tail.head)
+          else if (!isGuardedCase(currCase) || currCase.guard.tpe =:= ConstantType(Constant(true)))
+            unreachable = cases.tail.find(caseImplies(currCase))
+          else if (currCase.guard.tpe =:= ConstantType(Constant(false)))
+            unreachable = Some(currCase)
 
           cases = cases.tail
         }
@@ -3071,68 +3150,80 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       }
 
       // empty list ==> failure
-      def apply(cases: List[(Symbol, List[TreeMaker])], pt: Type): List[CaseDef] = {
-        val caseDefs = cases map { case (scrutSym, makers) =>
-          makers match {
-            // default case
-            case GuardAndBodyTreeMakers(guard, body) =>
-              Some(defaultCase(scrutSym, guard, body))
-            // constant (or typetest for typeSwitch)
-            case SwitchableTreeMaker(pattern) :: GuardAndBodyTreeMakers(guard, body) =>
-              Some(CaseDef(pattern, guard, body))
-            // alternatives
-            case AlternativesTreeMaker(_, altss, _) :: GuardAndBodyTreeMakers(guard, body) if alternativesSupported =>
-              val switchableAlts = altss map {
-                case SwitchableTreeMaker(pattern) :: Nil =>
-                  Some(pattern)
-                case _ =>
-                  None
-              }
+      def apply(cases: List[(Symbol, List[TreeMaker])], pt: Type): List[CaseDef] =
+        // generate if-then-else for 1 case switch (avoids verify error... can't imagine a one-case switch being faster than if-then-else anyway)
+        if (cases.isEmpty || cases.tail.isEmpty) Nil
+        else {
+          val caseDefs = cases map { case (scrutSym, makers) =>
+            makers match {
+              // default case
+              case GuardAndBodyTreeMakers(guard, body) =>
+                Some(defaultCase(scrutSym, guard, body))
+              // constant (or typetest for typeSwitch)
+              case SwitchableTreeMaker(pattern) :: GuardAndBodyTreeMakers(guard, body) =>
+                Some(CaseDef(pattern, guard, body))
+              // alternatives
+              case AlternativesTreeMaker(_, altss, _) :: GuardAndBodyTreeMakers(guard, body) if alternativesSupported =>
+                val switchableAlts = altss map {
+                  case SwitchableTreeMaker(pattern) :: Nil =>
+                    Some(pattern)
+                  case _ =>
+                    None
+                }
 
-              // succeed if they were all switchable
-              sequence(switchableAlts) map { switchableAlts =>
-                CaseDef(Alternative(switchableAlts), guard, body)
-              }
-            case _ =>
-              // patmatDebug("can't emit switch for "+ makers)
-              None //failure (can't translate pattern to a switch)
+                // succeed if they were all switchable
+                sequence(switchableAlts) map { switchableAlts =>
+                  CaseDef(Alternative(switchableAlts), guard, body)
+                }
+              case _ =>
+                // patmatDebug("can't emit switch for "+ makers)
+                None //failure (can't translate pattern to a switch)
+            }
           }
-        }
 
-        (for(
-          caseDefsWithGuards <- sequence(caseDefs);
-          collapsed = collapseGuardedCases(caseDefsWithGuards);
-          caseDefs <- checkNoGuards(collapsed)) yield {
-            if (!unchecked)
-              unreachableCase(caseDefs) foreach (cd => reportUnreachable(cd.body.pos))
-
-            // if we rewrote, we may need the default label to jump there (but then again, we may not)
-            // TODO: make more precise; we don't need the default label if
-            //  - all collapsed cases included an un-guarded case (some of the guards of each case will always be true)
-            //  - or: there was no default case (if all the guards of a case fail, it's a matcherror for sure)
-            val needDefaultLabel = (collapsed != caseDefsWithGuards)
-
-            def wrapInDefaultLabelDef(cd: CaseDef): CaseDef =
-              if (needDefaultLabel && canJump) deriveCaseDef(cd){ b =>
-                // TODO: can b.tpe ever be null? can't really use pt, see e.g. pos/t2683 or cps/match1.scala
-                defaultLabel setInfo MethodType(Nil, if (b.tpe != null) b.tpe else pt)
-                LabelDef(defaultLabel, Nil, b)
-              } else cd
-
-            (caseDefs partition isDefault) match {
-              case (Nil, caseDefs) => caseDefs :+ wrapInDefaultLabelDef(defaultCase())
-              case (default :: Nil, caseDefs) if canJump || !needDefaultLabel =>
-                // we either didn't collapse (and thus definitely didn't have to emit a jump),
-                // or we canJump (and then the potential jumps in collapsed are ok)
-                caseDefs :+ wrapInDefaultLabelDef(default)
-              case _ => Nil
-                // TODO: if (canJump) error message (but multiple defaults should be caught by unreachability)
-                // if (!canJump) we got ourselves in the situation where we might need to emit a jump when we can't (in exception handler)
-                //  --> TODO: refine the condition to detect whether we actually really needed to jump, but this seems relatively rare
+          val caseDefsWithGuards = sequence(caseDefs) match {
+            case None      => return Nil
+            case Some(cds) => cds
+          }
+
+          val allReachable =
+            if (unchecked) true
+            else {
+              val unreachables = unreachableCase(caseDefsWithGuards)
+              unreachables foreach {cd => reportUnreachable(cd.body.pos)}
+              // a switch with duplicate cases yields a verify error,
+              // and a switch with duplicate cases and guards cannot soundly be rewritten to an unguarded switch
+              // (even though the verify error would disappear, the behaviour would change)
+              unreachables.isEmpty
+            }
+
+          if (!allReachable) Nil
+          else if (noGuards(caseDefsWithGuards)) {
+            if (isDefault(caseDefsWithGuards.last)) caseDefsWithGuards
+            else caseDefsWithGuards :+ defaultCase()
+          } else {
+            // collapse identical cases with different guards, push guards into body for all guarded cases
+            // this translation is only sound if there are no unreachable (duplicate) cases
+            // it should only be run if there are guarded cases, and on failure it returns Nil
+            val (collapsed, needDefaultLabel) = collapseGuardedCases(caseDefsWithGuards)
+
+            if (collapsed.isEmpty || (needDefaultLabel && !canJump)) Nil
+            else {
+              def wrapInDefaultLabelDef(cd: CaseDef): CaseDef =
+                if (needDefaultLabel) deriveCaseDef(cd){ b =>
+                  // TODO: can b.tpe ever be null? can't really use pt, see e.g. pos/t2683 or cps/match1.scala
+                  defaultLabel setInfo MethodType(Nil, if (b.tpe != null) b.tpe else pt)
+                  LabelDef(defaultLabel, Nil, b)
+                } else cd
+
+              val last = collapsed.last
+              if (isDefault(last)) {
+                if (!needDefaultLabel) collapsed
+                else collapsed.init :+ wrapInDefaultLabelDef(last)
+              } else collapsed :+ wrapInDefaultLabelDef(defaultCase())
             }
           }
-        ) getOrElse Nil
-      }
+        }
     }
 
     class RegularSwitchMaker(scrutSym: Symbol, matchFailGenOverride: Option[Tree => Tree], val unchecked: Boolean) extends SwitchMaker {
diff --git a/src/reflect/scala/reflect/internal/TreeInfo.scala b/src/reflect/scala/reflect/internal/TreeInfo.scala
index 745065b024..7ba749ed2c 100644
--- a/src/reflect/scala/reflect/internal/TreeInfo.scala
+++ b/src/reflect/scala/reflect/internal/TreeInfo.scala
@@ -442,6 +442,9 @@ abstract class TreeInfo {
       }
 */
 
+  /** Is this case guarded? */
+  def isGuardedCase(cdef: CaseDef) = cdef.guard != EmptyTree
+
   /** Is this pattern node a sequence-valued pattern? */
   def isSequenceValued(tree: Tree): Boolean = unbind(tree) match {
     case Alternative(ts)            => ts exists isSequenceValued
diff --git a/test/files/neg/t5830.check b/test/files/neg/t5830.check
index 85cb84378f..726fac2a1e 100644
--- a/test/files/neg/t5830.check
+++ b/test/files/neg/t5830.check
@@ -1,4 +1,7 @@
 t5830.scala:6: error: unreachable code
     case 'a' => println("b") // unreachable
                        ^
-one error found
+t5830.scala:4: error: could not emit switch for @switch annotated match
+  def unreachable(ch: Char) = (ch: @switch) match {
+                                    ^
+two errors found
diff --git a/test/files/neg/t6011.check b/test/files/neg/t6011.check
new file mode 100644
index 0000000000..5b5a861e5b
--- /dev/null
+++ b/test/files/neg/t6011.check
@@ -0,0 +1,10 @@
+t6011.scala:4: error: unreachable code
+    case 'a' | 'c' => 1 // unreachable
+                      ^
+t6011.scala:10: error: unreachable code
+    case 'b' | 'a'  => 1 // unreachable
+                       ^
+t6011.scala:8: error: could not emit switch for @switch annotated match
+  def f2(ch: Char): Any = (ch: @annotation.switch) match {
+                                ^
+three errors found
diff --git a/test/files/neg/t6011.flags b/test/files/neg/t6011.flags
new file mode 100644
index 0000000000..e8fb65d50c
--- /dev/null
+++ b/test/files/neg/t6011.flags
@@ -0,0 +1 @@
+-Xfatal-warnings
\ No newline at end of file
diff --git a/test/files/neg/t6011.scala b/test/files/neg/t6011.scala
new file mode 100644
index 0000000000..a36cca7897
--- /dev/null
+++ b/test/files/neg/t6011.scala
@@ -0,0 +1,23 @@
+object Test {
+  def f(ch: Char): Any = ch match {
+    case 'a'  => 1
+    case 'a' | 'c' => 1 // unreachable
+  }
+
+  // won't be compiled to a switch since it has an unreachable (duplicate) case
+  def f2(ch: Char): Any = (ch: @annotation.switch) match {
+    case 'a' | 'b'  => 1
+    case 'b' | 'a'  => 1 // unreachable
+    case _ =>
+  }
+
+  // s'all good
+  def f3(ch: Char): Any = (ch: @annotation.switch) match {
+    case 'a' | 'b'  if (true: Boolean) => 1
+    case 'b' | 'a'  => 1 // ok
+    case _ => // need third case to check switch annotation (two-case switches are always okay to compile to if-then-else)
+  }
+
+
+  def main(args: Array[String]): Unit = f('a')
+}
\ No newline at end of file
diff --git a/test/files/neg/t6048.check b/test/files/neg/t6048.check
new file mode 100644
index 0000000000..051f41877e
--- /dev/null
+++ b/test/files/neg/t6048.check
@@ -0,0 +1,10 @@
+t6048.scala:3: error: unreachable code
+    case _ if false => x // unreachable
+                       ^
+t6048.scala:8: error: unreachable code
+    case _ if false => x // unreachable
+                       ^
+t6048.scala:14: error: unreachable code
+    case 5 if true  => x // unreachable
+                       ^
+three errors found
diff --git a/test/files/neg/t6048.flags b/test/files/neg/t6048.flags
new file mode 100644
index 0000000000..e8fb65d50c
--- /dev/null
+++ b/test/files/neg/t6048.flags
@@ -0,0 +1 @@
+-Xfatal-warnings
\ No newline at end of file
diff --git a/test/files/neg/t6048.scala b/test/files/neg/t6048.scala
new file mode 100644
index 0000000000..803e651d19
--- /dev/null
+++ b/test/files/neg/t6048.scala
@@ -0,0 +1,22 @@
+class A {
+  def f1(x: Int) = x match {
+    case _ if false => x // unreachable
+    case 5          => x
+  }
+
+  def f2(x: Int) = x match {
+    case _ if false => x // unreachable
+    case 5 if true  => x
+  }
+
+  def f3(x: Int) = x match {
+    case _ => x
+    case 5 if true  => x // unreachable
+  }
+
+  def test1(x: Int) = x match {
+    case c if c < 0 => 0
+    case 1          => 1
+    case _          => 2
+  }
+}
diff --git a/test/files/run/t6011b.check b/test/files/run/t6011b.check
new file mode 100644
index 0000000000..00750edc07
--- /dev/null
+++ b/test/files/run/t6011b.check
@@ -0,0 +1 @@
+3
diff --git a/test/files/run/t6011b.scala b/test/files/run/t6011b.scala
new file mode 100644
index 0000000000..3d405e0705
--- /dev/null
+++ b/test/files/run/t6011b.scala
@@ -0,0 +1,11 @@
+object Test extends App {
+  var cond = true
+
+  // should not generate a switch
+  def f(ch: Char): Int = ch match {
+    case 'a' if cond => 1
+    case 'z' | 'a' => 2
+  }
+
+  println(f('a') + f('z')) // 3
+}
\ No newline at end of file