Roadmap for Improving the Swift Type Checker
This is all, of course, about the dreaded
the compiler is unable to type-check this expression in reasonable timeerror. This error can appear with both valid and invalid code, and the various workarounds are unsatisfactory, to say the least. Splitting up an expression into smaller pieces, introducing type annotations, or attempting other refactorings will sometimes allow valid code to type check, or in the invalid case, surface an actionable diagnostic. However, this breaks flow and becomes a frustrating process of trial and error “shotgun debugging” even for the most experienced Swift programmers. The compiler doesn’t even tell you if your expression is valid or not![…]
For a more detailed overview of constraint solving in the Swift type checker, see swift/docs/TypeChecker.md at main · swiftlang/swift · GitHub. For an explanation of why overload resolution is inherently hard, and why every known approach has exponential running time in the worst case, see How does compiler compile SwiftUI code? - #4 by Slava_Pestov and Lambda Expressions vs. Anonymous Methods, Part Five | Microsoft Learn.
[…]
The main goal then, is to devise sufficiently-general heuristics which can quickly solve most realistic problem instances, without hard-coding too many special cases, so that hopefully, the exponential running time only appears with pathological examples which are unlikely to occur in practice. The primary way to accomplish this is to attempt disjunction choices in the right order---this includes both choosing the next disjunction to attempt, and the next choice within a disjunction to attempt. Also, we can avoid considering disjunction choices that lead to contradictions. By doing this, we can find the valid solutions more quickly, and spend less time exploring long “dead ends.”
A secondary goal is to improve the auxiliary data structures and algorithms used in the constraint solver, so that even if an exhaustive search must be attempted on a given expression, as will sometimes be the case, we burn less CPU time while considering the same search space.
I’m glad to see that this is being taken seriously and that they’re also considering minor source-breaking changes that could produce big benefits.
Previously:
- Swift 6.2: Approachable Concurrency
- Swift 6.2
- Rewriting the TypeScript Compiler in Go
- Swift at 10
- Compiling Swift Generics
- Swift Type Checking Is Undecidable
- Swift 5.3 Released
- Playing Jenga With Swift’s Type Checker
- The Secret Life of Types in Swift
- Exponential Time Complexity in the Swift Type Checker
- Speeding Up Slow Swift Build Times
- Swift Type-checking Performance Case Study
- Slow Swift Array Type Inference
