From ef2bf411427624b77c4c48a7303176f1664321a2 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Tue, 10 Jul 2012 15:10:12 +0200 Subject: 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). --- test/files/neg/t5830.check | 5 ++++- test/files/neg/t6011.check | 10 ++++++++++ test/files/neg/t6011.flags | 1 + test/files/neg/t6011.scala | 23 +++++++++++++++++++++++ test/files/neg/t6048.check | 10 ++++++++++ test/files/neg/t6048.flags | 1 + test/files/neg/t6048.scala | 22 ++++++++++++++++++++++ test/files/run/t6011b.check | 1 + test/files/run/t6011b.scala | 11 +++++++++++ 9 files changed, 83 insertions(+), 1 deletion(-) create mode 100644 test/files/neg/t6011.check create mode 100644 test/files/neg/t6011.flags create mode 100644 test/files/neg/t6011.scala create mode 100644 test/files/neg/t6048.check create mode 100644 test/files/neg/t6048.flags create mode 100644 test/files/neg/t6048.scala create mode 100644 test/files/run/t6011b.check create mode 100644 test/files/run/t6011b.scala (limited to 'test') 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 -- cgit v1.2.3