From 0c4a06f8409feac5ba99c0a8961210225dbd4936 Mon Sep 17 00:00:00 2001 From: liu fengyun Date: Thu, 6 Apr 2017 15:36:37 +0200 Subject: exhaustivity support for enums --- .../src/dotty/tools/dotc/config/Printers.scala | 1 + .../src/dotty/tools/dotc/transform/PostTyper.scala | 7 +- .../dotty/tools/dotc/transform/patmat/Space.scala | 112 ++++++++++++--------- tests/patmat/enumColor.scala | 12 +++ tests/patmat/patmat-indent.check | 2 +- tests/patmat/patmat-indent.scala | 2 +- tests/patmat/t6420.check | 2 +- tests/patmat/t7285.check | 2 +- tests/patmat/t7466.check | 2 +- 9 files changed, 86 insertions(+), 56 deletions(-) create mode 100644 tests/patmat/enumColor.scala diff --git a/compiler/src/dotty/tools/dotc/config/Printers.scala b/compiler/src/dotty/tools/dotc/config/Printers.scala index 002d0f933..a77607d18 100644 --- a/compiler/src/dotty/tools/dotc/config/Printers.scala +++ b/compiler/src/dotty/tools/dotc/config/Printers.scala @@ -31,4 +31,5 @@ object Printers { val cyclicErrors: Printer = noPrinter val pickling: Printer = noPrinter val inlining: Printer = noPrinter + val exhaustivity: Printer = noPrinter } diff --git a/compiler/src/dotty/tools/dotc/transform/PostTyper.scala b/compiler/src/dotty/tools/dotc/transform/PostTyper.scala index a0fe55a5b..bacb88091 100644 --- a/compiler/src/dotty/tools/dotc/transform/PostTyper.scala +++ b/compiler/src/dotty/tools/dotc/transform/PostTyper.scala @@ -111,7 +111,7 @@ class PostTyper extends MacroTransform with IdentityDenotTransformer { thisTran private def transformMemberDef(tree: MemberDef)(implicit ctx: Context): Unit = { val sym = tree.symbol - if (sym.is(CaseVal, butNot = Module | Method)) registerChild(sym, sym.info) + if (sym.is(CaseVal, butNot = Method | Module)) registerChild(sym, sym.info) sym.transformAnnotations(transformAnnot) } @@ -233,7 +233,10 @@ class PostTyper extends MacroTransform with IdentityDenotTransformer { thisTran // Add Child annotation to sealed parents unless current class is anonymous if (!sym.isAnonymousClass) // ignore anonymous class - sym.asClass.classInfo.classParents.foreach(registerChild(sym, _)) + sym.asClass.classInfo.classParents.foreach { parent => + val sym2 = if (sym.is(Module)) sym.sourceModule else sym + registerChild(sym2, parent) + } tree } diff --git a/compiler/src/dotty/tools/dotc/transform/patmat/Space.scala b/compiler/src/dotty/tools/dotc/transform/patmat/Space.scala index 8d926fcf0..41196014e 100644 --- a/compiler/src/dotty/tools/dotc/transform/patmat/Space.scala +++ b/compiler/src/dotty/tools/dotc/transform/patmat/Space.scala @@ -13,6 +13,7 @@ import core.StdNames._ import core.NameOps._ import core.Constants._ import reporting.diagnostic.messages._ +import config.Printers.{ exhaustivity => debug } /** Space logic for checking exhaustivity and unreachability of pattern matching * @@ -29,7 +30,6 @@ import reporting.diagnostic.messages._ * 4. For a case class Kon(x1: T1, x2: T2, .., xn: Tn), if S1, S2, ..., Sn * are spaces, then `Kon(S1, S2, ..., Sn)` is a space. * 5. A constant `Const(value, T)` is a point in space - * 6. A stable identifier `Var(sym, T)` is a space * * For the problem of exhaustivity check, its formulation in terms of space is as follows: * @@ -70,9 +70,6 @@ case class Or(spaces: List[Space]) extends Space /** Point in space */ sealed trait Point extends Space -/** Point representing variables(stable identifier) in patterns */ -case class Var(sym: Symbol, tp: Type) extends Point - /** Point representing literal constants in patterns */ case class Const(value: Constant, tp: Type) extends Point @@ -97,6 +94,9 @@ trait SpaceLogic { /** Get components of decomposable types */ def decompose(tp: Type): List[Space] + /** Display space in string format */ + def show(sp: Space): String + /** Simplify space using the laws, there's no nested union after simplify */ def simplify(space: Space): Space = space match { case Kon(tp, spaces) => @@ -137,7 +137,7 @@ trait SpaceLogic { def tryDecompose1(tp: Type) = canDecompose(tp) && isSubspace(Or(decompose(tp)), b) def tryDecompose2(tp: Type) = canDecompose(tp) && isSubspace(a, Or(decompose(tp))) - (a, b) match { + val res = (a, b) match { case (Empty, _) => true case (_, Empty) => false case (Or(ss), _) => ss.forall(isSubspace(_, b)) @@ -162,12 +162,11 @@ trait SpaceLogic { case (Const(_, _), Or(ss)) => ss.exists(isSubspace(a, _)) case (Const(_, _), _) => false case (_, Const(_, _)) => false - case (Var(x, _), Var(y, _)) => x == y - case (Var(_, tp1), Typ(tp2, _)) => isSubType(tp1, tp2) || tryDecompose2(tp2) - case (Var(_, _), Or(ss)) => ss.exists(isSubspace(a, _)) - case (Var(_, _), _) => false - case (_, Var(_, _)) => false } + + debug.println(s"${show(a)} < ${show(b)} = $res") + + res } /** Intersection of two spaces */ @@ -175,7 +174,7 @@ trait SpaceLogic { def tryDecompose1(tp: Type) = intersect(Or(decompose(tp)), b) def tryDecompose2(tp: Type) = intersect(a, Or(decompose(tp))) - (a, b) match { + val res = (a, b) match { case (Empty, _) | (_, Empty) => Empty case (_, Or(ss)) => Or(ss.map(intersect(a, _)).filterConserve(_ ne Empty)) case (Or(ss), _) => Or(ss.map(intersect(_, b)).filterConserve(_ ne Empty)) @@ -211,19 +210,11 @@ trait SpaceLogic { else if (canDecompose(tp1)) tryDecompose1(tp1) else Empty case (_, Const(_, _)) => Empty - case (Var(x, _), Var(y, _)) => - if (x == y) a else Empty - case (Var(_, tp1), Typ(tp2, _)) => - if (isSubType(tp1, tp2)) a - else if (canDecompose(tp2)) tryDecompose2(tp2) - else Empty - case (Var(_, _), _) => Empty - case (Typ(tp1, _), Var(_, tp2)) => - if (isSubType(tp2, tp1)) b - else if (canDecompose(tp1)) tryDecompose1(tp1) - else Empty - case (_, Var(_, _)) => Empty } + + debug.println(s"${show(a)} & ${show(b)} = ${show(res)}") + + res } /** The space of a not covered by b */ @@ -231,7 +222,7 @@ trait SpaceLogic { def tryDecompose1(tp: Type) = minus(Or(decompose(tp)), b) def tryDecompose2(tp: Type) = minus(a, Or(decompose(tp))) - (a, b) match { + val res = (a, b) match { case (Empty, _) => Empty case (_, Empty) => a case (Typ(tp1, _), Typ(tp2, _)) => @@ -275,15 +266,11 @@ trait SpaceLogic { if (canDecompose(tp1)) tryDecompose1(tp1) else a case (_, Const(_, _)) => a - case (Var(x, _), Var(y, _)) => - if (x == y) Empty else a - case (Var(_, tp1), Typ(tp2, _)) => - if (isSubType(tp1, tp2)) Empty - else if (canDecompose(tp2)) tryDecompose2(tp2) - else a - case (Var(_, _), _) => a - case (_, Var(_, _)) => a } + + debug.println(s"${show(a)} - ${show(b)} = ${show(res)}") + + res } } @@ -298,16 +285,14 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { */ def project(pat: Tree, roundUp: Boolean = true)(implicit ctx: Context): Space = pat match { case Literal(c) => Const(c, c.tpe) - case _: BackquotedIdent => Var(pat.symbol, pat.tpe) + case _: BackquotedIdent => Typ(pat.tpe, false) case Ident(_) | Select(_, _) => pat.tpe.stripAnnots match { case tp: TermRef => if (pat.symbol.is(Enum)) Const(Constant(pat.symbol), tp) - else if (tp.underlyingIterator.exists(_.classSymbol.is(Module))) - Typ(tp.widenTermRefExpr.stripAnnots, false) else - Var(pat.symbol, tp) + Typ(tp, false) case tp => Typ(tp, false) } case Alternative(trees) => Or(trees.map(project(_, roundUp))) @@ -345,7 +330,9 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { /** Is `tp1` a subtype of `tp2`? */ def isSubType(tp1: Type, tp2: Type): Boolean = { // check SI-9657 and tests/patmat/gadt.scala - erase(tp1) <:< erase(tp2) + val res = erase(tp1) <:< erase(tp2) + debug.println(s"${tp1.show} <:< ${tp2.show} = $res") + res } def isEqualType(tp1: Type, tp2: Type): Boolean = tp1 =:= tp2 @@ -373,6 +360,8 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { } } + debug.println(s"candidates for ${tp.show} : [${children.map(_.show).mkString(", ")}]") + tp match { case OrType(tp1, tp2) => List(Typ(tp1, true), Typ(tp2, true)) case _ if tp =:= ctx.definitions.BooleanType => @@ -385,7 +374,9 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { case _ => val parts = children.map { sym => if (sym.is(ModuleClass)) - sym.asClass.classInfo.selfType + refine(tp, sym.sourceModule.termRef) + else if (sym.isTerm) + refine(tp, sym.termRef) else if (sym.info.typeParams.length > 0 || tp.isInstanceOf[TypeRef]) refine(tp, sym.typeRef) else @@ -393,13 +384,26 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { } filter { tpe => // Child class may not always be subtype of parent: // GADT & path-dependent types - tpe <:< expose(tp) + val res = tpe <:< expose(tp) + if (!res) debug.println(s"unqualified child ousted: ${tpe.show} !< ${tp.show}") + res } + debug.println(s"${tp.show} decomposes to [${parts.map(_.show).mkString(", ")}]") + parts.map(Typ(_, true)) } } + // simplify p.Case$.This.m => p.Case.m + def simplifyPrefix(tp: Type): Type = tp match { + case tp @ ThisType(mcls: TypeRef) if mcls.symbol.sourceModule.exists => + TermRef(simplifyPrefix(mcls.prefix), mcls.symbol.sourceModule.asTerm) + case tp @ TypeRef(prefix, _) => tp.derivedSelect(simplifyPrefix(prefix)) + case tp @ TermRef(prefix, _) => tp.derivedSelect(simplifyPrefix(prefix)) + case _ => tp + } + /** Refine tp2 based on tp1 * * E.g. if `tp1` is `Option[Int]`, `tp2` is `Some`, then return @@ -409,20 +413,26 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { * `path2`, then return `path1.B`. */ def refine(tp1: Type, tp2: Type): Type = (tp1, tp2) match { - case (tp1: RefinedType, _) => tp1.wrapIfMember(refine(tp1.parent, tp2)) + case (tp1: RefinedType, _: TypeRef) => tp1.wrapIfMember(refine(tp1.parent, tp2)) case (tp1: HKApply, _) => refine(tp1.superType, tp2) - case (TypeRef(ref1: TypeProxy, _), tp2 @ TypeRef(ref2: TypeProxy, name)) => - if (ref1.underlying <:< ref2.underlying) TypeRef(ref1, name) else tp2 + case (TypeRef(ref1: TypeProxy, _), tp2 @ TypeRef(ref2: TypeProxy, _)) => + if (ref1.underlying <:< ref2.underlying) tp2.derivedSelect(ref1) else tp2 + case (TypeRef(ref1: TypeProxy, _), tp2 @ TermRef(ref2: TypeProxy, _)) => + if (ref1.underlying <:< ref2.underlying) tp2.derivedSelect(ref1) else tp2 case _ => tp2 } /** Abstract sealed types, or-types, Boolean and Java enums can be decomposed */ def canDecompose(tp: Type): Boolean = { - tp.classSymbol.is(allOf(Abstract, Sealed)) || + val res = tp.classSymbol.is(allOf(Abstract, Sealed)) || tp.classSymbol.is(allOf(Trait, Sealed)) || tp.isInstanceOf[OrType] || tp =:= ctx.definitions.BooleanType || tp.classSymbol.is(Enum) + + debug.println(s"decomposable: ${tp.show} = $res") + + res } /** Show friendly type name with current scope in mind @@ -475,13 +485,11 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { def doShow(s: Space, mergeList: Boolean = false): String = s match { case Empty => "" case Const(v, _) => v.show - case Var(x, _) => x.show + case Typ(tp: TermRef, _) => tp.symbol.showName case Typ(tp, decomposed) => val sym = tp.widen.classSymbol - if (sym.is(ModuleClass)) - showType(tp) - else if (ctx.definitions.isTupleType(tp)) + if (ctx.definitions.isTupleType(tp)) signature(tp).map(_ => "_").mkString("(", ", ", ")") else if (sym.showFullName == "scala.collection.immutable.::") if (mergeList) "_" else "List(_)" @@ -523,7 +531,9 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { } val Match(sel, cases) = tree - isCheckable(sel.tpe.widen.deAnonymize.dealiasKeepAnnots) + val res = isCheckable(sel.tpe.widen.deAnonymize.dealiasKeepAnnots) + debug.println(s"checkable: ${sel.show} = $res") + res } @@ -584,7 +594,11 @@ class SpaceEngine(implicit ctx: Context) extends SpaceLogic { val selTyp = sel.tpe.widen.deAnonymize.dealias - val patternSpace = cases.map(x => project(x.pat)).reduce((a, b) => Or(List(a, b))) + val patternSpace = cases.map({ x => + val space = project(x.pat) + debug.println(s"${x.pat.show} projects to ${show(space)}") + space + }).reduce((a, b) => Or(List(a, b))) val uncovered = simplify(minus(Typ(selTyp, true), patternSpace)) if (uncovered != Empty) diff --git a/tests/patmat/enumColor.scala b/tests/patmat/enumColor.scala new file mode 100644 index 000000000..60d610d0d --- /dev/null +++ b/tests/patmat/enumColor.scala @@ -0,0 +1,12 @@ + enum Color { + case Red, Green, Blue + } + + object Test { + def f(color: Color) = { + import Color._ + color match { + case Red | Green | Blue => + } + } +} diff --git a/tests/patmat/patmat-indent.check b/tests/patmat/patmat-indent.check index 79845ebcf..4f0ec4dd9 100644 --- a/tests/patmat/patmat-indent.check +++ b/tests/patmat/patmat-indent.check @@ -1,3 +1,3 @@ 9: Pattern Match Exhaustivity: Nil -23: Pattern Match Exhaustivity: _: Boolean +23: Pattern Match Exhaustivity: true, false 27: Pattern Match Exhaustivity: _: Int diff --git a/tests/patmat/patmat-indent.scala b/tests/patmat/patmat-indent.scala index ef25bb2c7..a2b18e7fb 100644 --- a/tests/patmat/patmat-indent.scala +++ b/tests/patmat/patmat-indent.scala @@ -1,5 +1,5 @@ object Test { - val Nil = scala.Nil + val Nil: scala.collection.immutable.Nil.type = scala.collection.immutable.Nil val X = 5 object Inner { diff --git a/tests/patmat/t6420.check b/tests/patmat/t6420.check index 73acf1454..c15701594 100644 --- a/tests/patmat/t6420.check +++ b/tests/patmat/t6420.check @@ -1 +1 @@ -5: Pattern Match Exhaustivity: (Nil, _), (List(_, _), _), (Nil, Nil), (Nil, List(_, _)), (List(_, _), Nil), (List(_, _), List(_, _)), (_, Nil), (_, List(_, _)) +5: Pattern Match Exhaustivity: (Nil, _), (List(true, _), _), (List(false, _), _), (_, Nil), (_, List(true, _)), (_, List(false, _)) diff --git a/tests/patmat/t7285.check b/tests/patmat/t7285.check index 1c2841920..d40b77e4b 100644 --- a/tests/patmat/t7285.check +++ b/tests/patmat/t7285.check @@ -1,3 +1,3 @@ 15: Pattern Match Exhaustivity: (Up, Down) 33: Pattern Match Exhaustivity: Down -51: Pattern Match Exhaustivity: (Base.Up, Base.Down) +51: Pattern Match Exhaustivity: (Up, Down) diff --git a/tests/patmat/t7466.check b/tests/patmat/t7466.check index 35227484e..af596399b 100644 --- a/tests/patmat/t7466.check +++ b/tests/patmat/t7466.check @@ -1 +1 @@ -8: Pattern Match Exhaustivity: (_, _) +8: Pattern Match Exhaustivity: (true, _), (false, _), (_, true), (_, false) -- cgit v1.2.3