mirror of
https://github.com/apple/swift.git
synced 2025-12-21 12:14:44 +01:00
671944df0c
The problem Assume 'A' and 'B' are enums with cases .a1, .a2, etc. and
.b1, .b2, etc. If we try to typecheck this switch:
switch (a, b) {
case (.a1, .b1),
(.a1, .b2):
break
...
The compiler is going to try to perform the following series of
operations:
> var s = (A, B)
> s -= (.a1, .b1)
((A - .a1, B) | (A, B - .b1))
> s -= (.a1, .b2)
(((A - .a1, B) | (A - .a1, B - .b2)) |
((A - .a1, B - .b1) | (A, B - .b1 - .b2)))
...
As you can see, the disjunction representing the uncovered space is
growing exponentially. Eventually some of these will start
disappearing (for instance, if B only has .b1 and .b2, that last term
can go away), and if the switch is exhaustive they can /all/ start
disappearing. But several of them are also redundant: the second and
third cases are fully covered by the first.
I exaggerated a little: the compiler is already smart enough to know
that the second case is redundant with the first, because it already
knows that (.a1, .b2) isn't a subset of (A - .a1, B). However, the
third and fourth cases are generated separately from the first two,
and so nothing ever checks that the third case is also redundant.
This patch changes the logic for subtracting from a disjunction so
that
1. any resulting disjunctions are flattened, and
2. any later terms that are subspaces of earlier terms are dropped
This is a quadratic algorithm in the worst case (compare every space
against every earlier space), but because it saves us from exponential
growth (or at least brings down the exponent) it's worth it. For the
test case now committed in the repository, we went from 40 seconds
(using -switch-checking-invocation-threshold=20000000 to avoid cutting
off early) to 0.2 seconds.
I'll admit I was only timing this one input, and it's possible that
other complex switches will not see the same benefit, or may even see
a slowdown. But I do think this kind of switch is common in both
hand-written and auto-generated code, and therefore this is likely to
be a benefit in many places.
rdar://problem/47365349
213 lines
4.4 KiB
Swift
213 lines
4.4 KiB
Swift
// RUN: %target-typecheck-verify-swift
|
|
|
|
enum NumericBase {
|
|
case binary
|
|
case ternary
|
|
case quaternary
|
|
case quinary
|
|
case senary
|
|
case septary
|
|
case octal
|
|
case nonary
|
|
case decimal
|
|
case undecimal
|
|
case duodecimal
|
|
}
|
|
|
|
enum Direction {
|
|
case left
|
|
case right
|
|
}
|
|
|
|
enum WritingSystem {
|
|
case logographic
|
|
case alphabet(kind: Alphabet)
|
|
case abjad
|
|
case abugida
|
|
case syllabary
|
|
case other
|
|
}
|
|
|
|
enum Alphabet {
|
|
case roman
|
|
case greek
|
|
case cyrillic
|
|
}
|
|
|
|
func test(base: NumericBase, direction: Direction, writingSystem: WritingSystem) {
|
|
switch (base, direction, writingSystem) {
|
|
case (.binary, .left, .logographic),
|
|
(.binary, .left, .alphabet),
|
|
(.binary, .left, .abugida):
|
|
break
|
|
|
|
case (.binary, .right, .logographic),
|
|
(.binary, .right, .alphabet),
|
|
(.binary, .right, .abugida):
|
|
break
|
|
|
|
case (.binary, _, .abjad):
|
|
break
|
|
|
|
case (.binary, _, .syllabary):
|
|
break
|
|
|
|
case (.ternary, .left, .logographic):
|
|
break
|
|
|
|
case (.ternary, .left, .alphabet),
|
|
(.ternary, .left, .abugida):
|
|
break
|
|
|
|
case (.ternary, .right, .logographic),
|
|
(.ternary, .right, .abugida):
|
|
break
|
|
|
|
case (.ternary, .right, .alphabet):
|
|
break
|
|
|
|
case (.ternary, _, .abjad):
|
|
break
|
|
|
|
case (.ternary, _, .syllabary):
|
|
break
|
|
|
|
case (.quaternary, .left, .logographic):
|
|
break
|
|
|
|
case (.quaternary, .left, .alphabet),
|
|
(.quaternary, .left, .abugida):
|
|
break
|
|
|
|
case (.quaternary, .right, .logographic),
|
|
(.quaternary, .right, .abugida):
|
|
break
|
|
|
|
case (.quaternary, .right, .alphabet):
|
|
break
|
|
|
|
case (.quaternary, _, .abjad):
|
|
break
|
|
|
|
case (.quaternary, _, .syllabary):
|
|
break
|
|
|
|
case (.quinary, .left, .logographic),
|
|
(.senary, .left, .logographic):
|
|
break
|
|
|
|
case (.quinary, .left, .alphabet),
|
|
(.senary, .left, .alphabet),
|
|
(.quinary, .left, .abugida),
|
|
(.senary, .left, .abugida):
|
|
break
|
|
|
|
case (.quinary, .right, .logographic),
|
|
(.senary, .right, .logographic):
|
|
break
|
|
|
|
case (.quinary, .right, .alphabet),
|
|
(.senary, .right, .alphabet),
|
|
(.quinary, .right, .abugida),
|
|
(.senary, .right, .abugida):
|
|
break
|
|
|
|
case (.quinary, _, .abjad),
|
|
(.senary, _, .abjad):
|
|
break
|
|
|
|
case (.quinary, _, .syllabary),
|
|
(.senary, _, .syllabary):
|
|
break
|
|
|
|
case (.septary, .left, .logographic):
|
|
break
|
|
|
|
case (.septary, .left, .alphabet),
|
|
(.septary, .left, .abugida):
|
|
break
|
|
|
|
case (.septary, .right, .logographic):
|
|
break
|
|
|
|
case (.septary, .right, .alphabet),
|
|
(.septary, .right, .abugida):
|
|
break
|
|
|
|
case (.septary, _, .abjad):
|
|
break
|
|
|
|
case (.septary, _, .syllabary):
|
|
break
|
|
|
|
case (.decimal, .left, .logographic):
|
|
break
|
|
|
|
case (.decimal, .left, .alphabet),
|
|
(.decimal, .left, .abugida):
|
|
break
|
|
|
|
case (.decimal, .right, .logographic):
|
|
break
|
|
|
|
case (.decimal, .right, .alphabet),
|
|
(.decimal, .right, .abugida):
|
|
break
|
|
|
|
case (.octal, .left, .logographic),
|
|
(.nonary, .left, .logographic):
|
|
break
|
|
|
|
case (.octal, .left, .alphabet),
|
|
(.nonary, .left, .alphabet),
|
|
(.octal, .left, .abugida),
|
|
(.nonary, .left, .abugida):
|
|
break
|
|
|
|
case (.octal, .right, .logographic),
|
|
(.nonary, .right, .logographic):
|
|
break
|
|
|
|
case (.octal, .right, .alphabet),
|
|
(.nonary, .right, .alphabet),
|
|
(.octal, .right, .abugida),
|
|
(.nonary, .right, .abugida):
|
|
break
|
|
|
|
case (.octal, _, .abjad),
|
|
(.nonary, _, .abjad),
|
|
(.decimal, _, .abjad):
|
|
break
|
|
|
|
case (.octal, _, .syllabary),
|
|
(.nonary, _, .syllabary),
|
|
(.decimal, _, .syllabary):
|
|
break
|
|
|
|
case (.undecimal, .left, .logographic):
|
|
break
|
|
|
|
case (.undecimal, .left, .alphabet),
|
|
(.undecimal, .left, .abugida):
|
|
break
|
|
|
|
case (.undecimal, .right, .logographic):
|
|
break
|
|
|
|
case (.undecimal, .right, .alphabet),
|
|
(.undecimal, .right, .abugida):
|
|
break
|
|
|
|
case (.undecimal, _, .abjad):
|
|
break
|
|
|
|
case (.undecimal, _, .syllabary):
|
|
break
|
|
|
|
case (.duodecimal, _, _):
|
|
break
|
|
case (_, _, .other):
|
|
break
|
|
}
|
|
}
|