Hi everyone!
For GSoC 2023, I worked with my mentor, @xedin, to explore how to rework type inference for key path expressions to help reduce errors and improve diagnostics and performance. This project built upon my work on the type inference debug output last summer so I was able to rely on that work to understand what the output should print if the type checked process was fixed. I encountered a bit of a learning curve in understanding the key path type checking process and @xedin helped me tackle this by spending considerable time explaining various pathways in type checker code. We also had incredibly enlightening discussions about how various design decisions would impact other parts of the type checker process and I enormously appreciate his patience, time, and mentorship!
Key Path Type Inference
Previously, type inference for key path expressions followed the same type-checking process as most other Swift expressions - generate type constraints and variables for subexpressions and their interrelationships, find concrete types for each type variable, and apply this solution to produce a fully typed expression. However, for some key path expressions, this process failed to successfully type-check and instead produced several errors, including the infamous “type of expression is ambiguous without more context.” The type checker tried to evaluate key path components to determine key path characteristics but then struggled to reconnect this information to the key path expression itself. Ultimately, the type-checker would fail to determine a set of concrete types and relationships for a key path’s expression and components, and instead report a failure to type-check the input expression.
Updating the Key Path Type Checking Process
In part, the Swift type-checker struggled to determine the correct capabilities for key path components because it attempted to do so before all of its components were fully resolved. Essentially, it tried to resolve the key path related component types too early and had no effective mechanism for reactivating related constraints later in the process, which caused important information about key path capabilities to go missing during constraint solving.
To solve this issue, we took inspiration from how Swift closure type-checking is set up - closure bodies are type-checked only after a contextual type for a closure is determined. Similarly, by delaying key path expression type checking until a contextual type has been discovered, we could check if the key path expression capabilities matched the contextual capabilities. Upon the availability of a contextual type, the key path’s components are sequentially checked to evaluate the key path expression’s capabilities which are then compared to the contextual type. The type checker is then able to deliver a successfully type checked expression or offer diagnostics that describe mismatched key path root, values, capabilities, etc.
Let's illustrate this process with the following invalid code sample:
struct User {
var name: Name
}
struct Name {
let firstName: String
}
func test(_: WritableKeyPath<User, String>) {}
test(\.name.firstName) // error: cannot convert value of type 'KeyPath<User, String>' to expected argument type 'WritableKeyPath<User, String>'
The type checker first resolves a contextual type of WritableKeyPath<User, String> and then attempts to match the capabilities of the last chained component firstName (which is read-only as firstName is a let) with the key path expression capabilities of WritableKeyPath, which are not a match and a diagnostic is delivered on the first argument of test().
This effort to delay key path expression type checking led to several related code design quandaries where this “fix” solved the original problem but now resulted in failures to type-check some valid expressions that relied on the original pattern or produced worse diagnostics. Briefly, here are a few of the problems we encountered that required new creative fixes to work with the updated delayed solution:
- We assumed that by waiting until a contextual type was determined we would have both a concrete key path base and value type. However, this approach failed for key paths with chained components where the final key path component produced a value type that is a subtype of a contextual value type. Chained components were resolved later in the type checking process so we were not guaranteed to have a resolved key path value despite finding a contextual type for the key path expression. Delaying key path value resolution until the components were evaluated and the key path value type variable was bound helped us circumvent this issue.
class A {}
class B : A {}
struct S {
var value: B
}
let _: KeyPath<S, A> = \.value
In the example above, if the type checker binds the key path type to a contextual type of KeyPath<S, A>, then it will subsequently bind the key path value to A, which is invalid because the reference to member value is type B.The subtyping relationship between the last component and the key path value type must be maintained so that the type checker does not attempt to bind the latter from context.
- The original implementation did not impose any constraints on what kind of type key path expression could be bound to but semantically key path expression can only be bound to a key path that has both
RootandValue, which meant that we had to adjust inference to prevent the type-checker from binding key path expression type to fully erasedAnyKeyPathand partially erasedPartialKeyPathtypes when the type comes from the context.
struct A {
var value: Int
}
let kpLiteral = \A.value // type checker infers expression as KeyPath and binds KeyPath<A, Int> as keypath type
let kpWithContextualType: PartialKeyPath<A> = \A.value // type checker infers expression as KeyPath, then type erased into PartialKeyPath and binds PartialKeyPath<A> as keypath type
- Similarly to #2, the change in behavior exposed issues related to conversions between function types and key path types introduced by SE-0249 because eagerly binding a key path type meant that some previously allowed conversion was no longer possible.
func provideKPValueButNotRoot<T>(_ kp: KeyPath<T, String>) {}
provideKPValueButNotRoot(\String.foo) // error: value of type ‘String’ has no member ‘foo’
// removed error: generic parameter 'T' could not be inferred
Here a second diagnostic that required a value for T was removed as that was a result of the type checker attempting to resolve T before resolving the key path type.
As a result of this work, the type checker evaluates key path expressions more efficiently with better diagnostics and fewer ambiguities, and with an improved key path implementation in the Swift compiler.
Other Thoughts & Next Steps
I tremendously enjoyed working on this project with @xedin! It was a challenge that allowed me to deepen my understanding of the solver implementation, utilize improvements I made to the debug output, and make more impactful changes to the compiler codebase. Refactoring the debug output helped me understand how the various information collected by the type checker is evaluated to assign types from context. Taking a look at key path expression type checking failures revealed some of the fallibilities of the constraint system and solver and how design decisions choices that solve certain issues can cause others.
Working with the Swift toolchain has also become decidedly easier since I first began contributing to the Swift compiler, and I’d like to thank everyone who has improved the documentation and tooling. I spent countless hours during the debug output project getting the compiler setup to work on Xcode that I was able to avoid this time around thanks to this work.
Finally, while working on key path inference, I realized there was opportunity to extend key path expressions and allow them to refer to static members. To that end, I am currently working on a pitch for metatype key paths. I believe that metatype keypaths could be a natural improvement to language semantics and the key implementation in the Swift compiler and I look forward to your discussion on that when it is published!
Do you think they'll land in the Xcode 15.3/Swift 5.10 beta series?