Add a size heuristic to the Space Engine
<rdar://32480026>
This is a particularly tricky tradeoff to have to make here. On the one
hand, we want diagnostics about incomplete patterns to provide as much
information as possible. On the other, pattern matrices grow
quasi-factorially in the size of the argument. That is, an enum with 10
cases that is switched on as a 2-tuple/argument list creates a total
subspace covering of size 100. For sufficiently large inputs, this can
DOS the Swift compiler.
It is simply not useful to present more than about 100 notes to the
user, nor is it useful to waste an enormous amount of time trying to
compute these subspaces for the limited information the diagnostic will
provide. Instead, short circuit if the size of the enum is above some
arbitrary threshold (currently 128) and just offer to add a 'default'.
Notably, this change is not *technically* source compatible in that it
ignores the new '@_downgrade_exhaustivity_check'. However to hit up
against this heuristic would require the user to be switching over four
DispatchTimeIntervals in a quadruple or using an equivalently-sized
enormous enum case. At which point we're hitting on the very reason
this heuristic exists.
There are definitely other, more informative, paths that we can take
here. GHC, for example, seems to run a highly limited form of space
subtraction when the input space is too large, and simply reports the
top 3 missing cases along with some ellipses. For now, I just want to
cut off this hang in the compiler.
diff --git a/lib/Sema/TypeCheckSwitchStmt.cpp b/lib/Sema/TypeCheckSwitchStmt.cpp
index e47f04c..bfb590e 100644
--- a/lib/Sema/TypeCheckSwitchStmt.cpp
+++ b/lib/Sema/TypeCheckSwitchStmt.cpp
@@ -71,7 +71,7 @@
};
#define PAIRCASE(XS, YS) case PairSwitch(XS, YS)
-
+
class Space final {
private:
SpaceKind Kind;
@@ -79,6 +79,60 @@
Identifier Head;
std::forward_list<Space> Spaces;
+ // NB: This constant is arbitrary. Anecdotally, the Space Engine is
+ // capable of efficiently handling Spaces of around size 200, but it would
+ // potentially push an enormous fixit on the user.
+ static const size_t MAX_SPACE_SIZE = 128;
+
+ size_t computeSize(TypeChecker &TC,
+ SmallPtrSetImpl<TypeBase *> &cache) const {
+ switch (getKind()) {
+ case SpaceKind::Empty:
+ return 0;
+ case SpaceKind::BooleanConstant:
+ return 1;
+ case SpaceKind::Type: {
+ if (!canDecompose(getType())) {
+ return 1;
+ }
+ cache.insert(getType().getPointer());
+
+ SmallVector<Space, 4> spaces;
+ decompose(TC, getType(), spaces);
+ size_t acc = 0;
+ for (auto &sp : spaces) {
+ // Decomposed pattern spaces grow with the sum of the subspaces.
+ acc += sp.computeSize(TC, cache);
+ }
+
+ cache.erase(getType().getPointer());
+ return acc;
+ }
+ case SpaceKind::Constructor: {
+ size_t acc = 1;
+ for (auto &sp : getSpaces()) {
+ // Break self-recursive references among enum arguments.
+ if (sp.getKind() == SpaceKind::Type
+ && cache.count(sp.getType().getPointer())) {
+ continue;
+ }
+
+ // Constructor spaces grow with the product of their arguments.
+ acc *= sp.computeSize(TC, cache);
+ }
+ return acc;
+ }
+ case SpaceKind::Disjunct: {
+ size_t acc = 0;
+ for (auto &sp : getSpaces()) {
+ // Disjoint grow with the sum of the subspaces.
+ acc += sp.computeSize(TC, cache);
+ }
+ return acc;
+ }
+ }
+ }
+
public:
explicit Space(Type T)
: Kind(SpaceKind::Type), TypeAndVal(T, false), Head(Identifier()),
@@ -100,6 +154,15 @@
void dump() const LLVM_ATTRIBUTE_USED;
+ size_t getSize(TypeChecker &TC) const {
+ SmallPtrSet<TypeBase *, 4> cache;
+ return computeSize(TC, cache);
+ }
+
+ static size_t getMaximumSize() {
+ return MAX_SPACE_SIZE;
+ }
+
bool isEmpty() const { return getKind() == SpaceKind::Empty; }
bool canDowngrade() const {
@@ -863,6 +926,7 @@
}
bool sawDowngradablePattern = false;
+ bool sawRedundantPattern = false;
SmallVector<Space, 4> spaces;
for (unsigned i = 0, e = Switch->getCases().size(); i < e; ++i) {
auto *caseBlock = Switch->getCases()[i];
@@ -880,6 +944,8 @@
sawDowngradablePattern);
if (projection.isUseful()
&& projection.isSubspace(Space(spaces), TC)) {
+ sawRedundantPattern |= true;
+
TC.diagnose(caseItem.getStartLoc(),
diag::redundant_particular_case)
.highlight(caseItem.getSourceRange());
@@ -890,6 +956,23 @@
Space totalSpace(Switch->getSubjectExpr()->getType());
Space coveredSpace(spaces);
+ size_t totalSpaceSize = totalSpace.getSize(TC);
+ if (totalSpaceSize > Space::getMaximumSize()) {
+ // Because the space is large, we have to extend the size
+ // heuristic to compensate for actually exhaustively pattern matching
+ // over enormous spaces. In this case, if the covered space covers
+ // as much as the total space, and there were no duplicates, then we
+ // can assume the user did the right thing and that they don't need
+ // a 'default' to be inserted.
+ if (!sawRedundantPattern
+ && coveredSpace.getSize(TC) >= totalSpaceSize) {
+ return;
+ }
+
+ diagnoseMissingCases(TC, Switch, /*justNeedsDefault*/true, Space());
+ return;
+ }
+
auto uncovered = totalSpace.minus(coveredSpace, TC).simplify(TC);
if (uncovered.isEmpty()) {
return;
diff --git a/test/Sema/exhaustive_switch.swift b/test/Sema/exhaustive_switch.swift
index 0ea73f2..24c0200 100644
--- a/test/Sema/exhaustive_switch.swift
+++ b/test/Sema/exhaustive_switch.swift
@@ -329,7 +329,7 @@
case (.hat, .spoon):
break
}
-
+
switch (x!, x!) { // expected-error {{switch must be exhaustive}}
// expected-note@-1 {{add missing case: '(.fork, _)'}}
// expected-note@-2 {{add missing case: '(.hat, .spoon)'}}
@@ -343,3 +343,158 @@
break
}
}
+
+enum LargeSpaceEnum {
+ case case0
+ case case1
+ case case2
+ case case3
+ case case4
+ case case5
+ case case6
+ case case7
+ case case8
+ case case9
+ case case10
+}
+
+func notQuiteBigEnough() -> Bool {
+ switch (LargeSpaceEnum.case1, LargeSpaceEnum.case2) { // expected-error {{switch must be exhaustive}}
+ // expected-note@-1 110 {{add missing case:}}
+ case (.case0, .case0): return true
+ case (.case1, .case1): return true
+ case (.case2, .case2): return true
+ case (.case3, .case3): return true
+ case (.case4, .case4): return true
+ case (.case5, .case5): return true
+ case (.case6, .case6): return true
+ case (.case7, .case7): return true
+ case (.case8, .case8): return true
+ case (.case9, .case9): return true
+ case (.case10, .case10): return true
+ }
+}
+
+enum OverlyLargeSpaceEnum {
+ case case0
+ case case1
+ case case2
+ case case3
+ case case4
+ case case5
+ case case6
+ case case7
+ case case8
+ case case9
+ case case10
+ case case11
+}
+
+func quiteBigEnough() -> Bool {
+ switch (OverlyLargeSpaceEnum.case1, OverlyLargeSpaceEnum.case2) { // expected-error {{switch must be exhaustive}}
+ // expected-note@-1 {{do you want to add a default clause?}}
+ case (.case0, .case0): return true
+ case (.case1, .case1): return true
+ case (.case2, .case2): return true
+ case (.case3, .case3): return true
+ case (.case4, .case4): return true
+ case (.case5, .case5): return true
+ case (.case6, .case6): return true
+ case (.case7, .case7): return true
+ case (.case8, .case8): return true
+ case (.case9, .case9): return true
+ case (.case10, .case10): return true
+ case (.case11, .case11): return true
+ }
+
+ // No diagnostic
+ switch (OverlyLargeSpaceEnum.case1, OverlyLargeSpaceEnum.case2) { // expected-error {{switch must be exhaustive}}
+ // expected-note@-1 {{do you want to add a default clause?}}
+ case (.case0, _): return true
+ case (.case1, _): return true
+ case (.case2, _): return true
+ case (.case3, _): return true
+ case (.case4, _): return true
+ case (.case5, _): return true
+ case (.case6, _): return true
+ case (.case7, _): return true
+ case (.case8, _): return true
+ case (.case9, _): return true
+ case (.case10, _): return true
+ }
+
+
+ // No diagnostic
+ switch (OverlyLargeSpaceEnum.case1, OverlyLargeSpaceEnum.case2) {
+ case (.case0, _): return true
+ case (.case1, _): return true
+ case (.case2, _): return true
+ case (.case3, _): return true
+ case (.case4, _): return true
+ case (.case5, _): return true
+ case (.case6, _): return true
+ case (.case7, _): return true
+ case (.case8, _): return true
+ case (.case9, _): return true
+ case (.case10, _): return true
+ case (.case11, _): return true
+ }
+
+ // No diagnostic
+ switch (OverlyLargeSpaceEnum.case1, OverlyLargeSpaceEnum.case2) {
+ case (_, .case0): return true
+ case (_, .case1): return true
+ case (_, .case2): return true
+ case (_, .case3): return true
+ case (_, .case4): return true
+ case (_, .case5): return true
+ case (_, .case6): return true
+ case (_, .case7): return true
+ case (_, .case8): return true
+ case (_, .case9): return true
+ case (_, .case10): return true
+ case (_, .case11): return true
+ }
+
+ // No diagnostic
+ switch (OverlyLargeSpaceEnum.case1, OverlyLargeSpaceEnum.case2) {
+ case (_, _): return true
+ }
+
+ // No diagnostic
+ switch (OverlyLargeSpaceEnum.case1, OverlyLargeSpaceEnum.case2) {
+ case (.case0, .case0): return true
+ case (.case1, .case1): return true
+ case (.case2, .case2): return true
+ case (.case3, .case3): return true
+ case _: return true
+ }
+}
+
+indirect enum InfinitelySized {
+ case one
+ case two
+ case recur(InfinitelySized)
+ case mutualRecur(MutuallyRecursive, InfinitelySized)
+}
+
+indirect enum MutuallyRecursive {
+ case one
+ case two
+ case recur(MutuallyRecursive)
+ case mutualRecur(InfinitelySized, MutuallyRecursive)
+}
+
+func infinitelySized() -> Bool {
+ switch (InfinitelySized.one, InfinitelySized.one) { // expected-error {{switch must be exhaustive}}
+ // expected-note@-1 10 {{add missing case:}}
+ case (.one, .one): return true
+ case (.two, .two): return true
+ }
+
+ switch (MutuallyRecursive.one, MutuallyRecursive.one) { // expected-error {{switch must be exhaustive}}
+ // expected-note@-1 10 {{add missing case:}}
+ case (.one, .one): return true
+ case (.two, .two): return true
+ }
+}
