Thanks for the detailed response! I've written up a rough draft based on your clarifications and @codafi's post. I've pasted the draft below, but I have a few more questions before we jump in:
- In the proposal below I added a
SymbolTable type for caching as suggested in the project description. However, Robert's response suggests we might be able to maintain a narrower scope without one. Would you recommend removing SymbolTable from the proposal?
- Based on Robert's post, should access control be considered explicitly out of scope for this project?
- I'm unsure how module lookup fits into this more narrowly scoped vision. If the API operates on a single
SourceFileSyntax, how can we perform cross-module lookup?
- I understand that correctness and documentation are both crucial for this project. Beyond choosing efficient algorithms and avoiding excessive copying, is performance optimization a primary objective?
- I'm not entirely sure how to handle implicit conformances, such as enums automatically conforming to
Hashable and RawRepresentable. Would it make sense to conservatively emit a lookForImplicitConformances result for enums without payloads in order to handle Hashable? Further, can we treat enum MyEnum: String as a lookForSupertype query?
The proposal is still a rough draft, and I'd really appreciate feedback on the overall format, scope and implementation plan. Thanks again for your guidance!
Abstract
We propose reimplementing the compiler’s qualified name lookup in the SwiftSyntax pure-Swift package. Hoisting this API onto the higher-level SwiftSyntax package surfaces essential semantic information, and will enable build tools with more powerful code transformations and more precise diagnostics.
Introduction
Swift Syntax is a Swift package that gives build tools and macros the ability to inspect and manipulate the Swift Abstract Syntax Tree (AST). From formatters to testing and UI-framework macros, the package’s all-Swift parser offers a powerful API that the 2024 GSoC project entitled “Lexical Scopes - A Scope Lookup Library for swift-syntax” expands upon with Unqualified Lookup. Unqualified lookup takes a bare identifier and finds what declaration it refers to; for instance:
extension Array where Element == Int {
var hasZeros: Bool {
var count = 0
for n in self where n == 0 { count += 1 }
return count == 0 // ⬅️ Look up `count` here
}
}
The lookup in the indicated position returns count and issues additional lookup requests. But how would we look up a member-access expression like MyType.f? Qualified lookup allows us to look into a nominal type declaration and find relevant declarations, providing another powerful AST facility that will allow build tools to build even more powerful macros and libraries.
Motivation
The proposed qualified lookup would fill the gap between the simple parsing facilities that SwiftSyntax currently provides and more advanced AST queries for which libraries usually resort to SourceKitten to communicate to the compiler backend. The current approach presents usability and distribution challenges. SourceKitten has to dynamically link the compiler backend’s SourceKit library, causing a multitude of hard-to-debug linker errors, especially on non-MacOS platforms like Linux. As evidenced by SwiftParser, implementing SwiftSyntax entirely in Swift can also increase performance by up to 8%.
There’s already evidence that existing SourceKitten clients want to take advantage of SwiftSyntax’s more advanced AST facilities. For example, SwiftLint is a very popular package utilizing both SourceKitten and SwiftSyntax, which now uses the 2024 GSoC project’s SwiftLexicalScopes library. In the code example above, SwiftLint will issue an unqualified name lookup query to determine if the user is using count == 0 rather than the more idiomatic isEmpty (where the unqualified lookup determines if count is a local variable where we shouldn’t throw an error). However, SwiftLint currently doesn’t check if the type actually contains a count property, a query which we could answer with qualified lookup.
Qualified lookup will provide a pure-Swift, reliable solution for build tools to reason about a type’s members. This lookup will enable new, more powerful macros and bring existing tooling like SwiftLint a step closer to removing SourceKit and resolve the corresponding distribution issues.
Related Work
This project mirrors compiler semantics but operates purely on SwiftSyntax trees without type-checking. Other SourceKit-based projects ultimately invoke the compiler with the aforementioned shortcomings.
Deliverables
Qualified Lookup API
I’ll add a new API to DeclGroupSyntax which includes nominal types, protocols and extensions. This API will include a stateless version and a SymbolTable version that caches results. Note that this project does not attempt overload resolution, constraint solving, operator lookup, or AnyObject dynamic lookup; these are left for the client to handle.
struct SymbolTable {
/// Construct a table for caching symbol lookup
/// for the given file syntax.
init(fileSyntax: SourceFileSyntax)
}
extension DeclGroupSyntax {
/// Search for members matching given identifier.
/// Parameters:
/// - lookUpPosition: Indicates position where we should
/// start lookup. Will enable future expansion that filters
/// by access control.
func lookupMember(
_ identifier: Identifier?,
from lookUpPosition: AbsolutePosition?,
with config: QualifiedLookupConfig = QualifiedLookupConfig()
) -> [QualifiedLookupResult]
// Same as above but can look up supertypes in SymbolTable
func lookupMember(
_ identifier: Identifier?,
from lookUpPosition: AbsolutePosition?,
using symbolTable: inout SymbolTable,
with config: QualifiedTableLookupConfig = QualifiedTableLookupConfig()
) -> [QualifiedLookupResult]
}
struct QualifiedLookupConfig {
init(configuredRegions: ConfiguredRegions? = nil)
}
struct QualifiedTableLookupConfig {
/// Parameters:
/// - lookupSuperprotocols: Whether to recursively look up inherited or
/// conformed-to protocols.
/// - lookupSuperclasses: Whether to recursively look up superclasses, and
/// the protocols they conform to (if `lookupSuperprotocols` is enabled).
init(lookupSuperprotocols: Bool = true, lookupSuperclasses: Bool = true,
configuredRegions: ConfiguredRegions? = nil)
}
enum QualifiedLookupResult {
/// Explicitly declared members.
///
/// Includes static/class/instance stored and computed properties,
/// functions, subscripts and initializers, dynamic-member-lookup
/// results, along with nested types, type aliases and associated types.
//// E.g.
/// ```
/// struct MyStruct<T> {
/// func callAsFunction() {}
/// }
/// ```
/// Qualified lookup within the `MyStruct` scope would
/// return the `callAsFunction()` function declaration.
/// Note that qualified lookup won't surface
/// operator functions, objc functions using dynamic lookup, and generic
/// parameters like `MyStruct.T` (semantically wrong).
case members([DeclSyntax], introducedIn: DeclSyntax)
/// Members declared in conditional extensions, e.g.
/// ```
/// extension Array where Element == Int {
/// func sum() -> Int { reduce(0, +) }
/// }
/// ```
/// Qualified lookup will return the `sum()` declaration in
/// the extension above together with the `where Element == Int` clause.
case conditionalMembers([DeclSyntax], introducedIn: DeclSyntax,
inheritanceClause: InheritanceClauseSyntax?, genericClause: GenericWhereClauseSyntax?)
/// Implicit members in the given group declaration like `self`,
/// `Type` and synthesized initializers.
case implicitMembers([DeclSyntax], introducedIn: DeclGroupSyntaxType)
/// Types and protocols annotated with `@dynamicMemberLookup` have one or
/// more subscripts with a `dynamicMember` string or keypath argument. We defer
/// to the type-checker to determine what members these subscripts can produce.
case lookForDynamicMembers(dynamicMemberSubscripts: [SubscriptDeclSyntax],
introducedIn: DeclGroupSyntaxType)
/// Any unknown attributes that could be attached macros or property wrappers
/// that expand to more declarations, e.g.
/// ```swift
/// struct MyView {
/// @State var myState = 0
/// }
/// ```
/// In this case, we instruct the tooling to look up what the `@State`
/// attribute expands to in the variable declaration above (if anything).
case lookForMacros(potentialMacroDecl: [DeclSyntax], introducedIn: DeclGroupSyntaxType)
/// Look for any types we encountered in the lookup that weren't in the
/// SymbolTable syntax trees (e.g. the looked up type conforms to a
/// protocol from a different module).
case lookForSupertypes(inheritedFrom: InheritanceClauseSyntax, genericClause: GenericWhereClauseSyntax?)
}
The SymbolTable implementation will maintain a mapping of type names to their member declarations. It will also keep track of requests to avoid cycles like the compiler’s existing NameLookupRequests.cpp does.
Integration with Unqualified Lookup
Then, we’ll add SymbolTable support to the existing unqualified lookup API to handle some of the lookForMembers requests:
extension SyntaxProtocol {
func lookup(
_ identifier: Identifier?,
using symbolTable: inout SymbolTable,
with config: LookupConfig = LookupConfig()
) -> [LookupResult]
}
extension ScopeSyntax {
func lookup(
_ identifier: Identifier?,
at lookUpPosition: AbsolutePosition,
using symbolTable: inout SymbolTable,
with config: LookupConfig
) -> [LookupResult]
}
Test Suite
I’ll perform extensive integration testing inspired by the compiler’s NameLookup tests. Further, since we'll surface a stateless API, we can add more targeted tests for specific lookup types; for instance, expect a lookForMacros result instead of immediately resolving the macro expansion. Additionally, I’ll perform simple benchmarks to identify crucial performance bottlenecks.
Documentation
All public APIs will explain their behavior through docstrings, offering examples and outlining edge cases. Additionally, I will add two more articles to the existing SwiftLexicalLookup DocC directory: one to explain the high-level interface with examples, and another describing the lower-level rules of qualified lookup.
Potential Challenges
Due to its expressivity, Swift has a lot of intersecting language features. While this proposal identifies some less evident cases of lookup like dynamicMemberLookup and the handling of macro expansions, there could be other unexpected syntactic constructs we need to handle. Despite its thorough outline, the 2024 Unqualified Lookup GSoC project ran into unexpected issues with guard statements. So since this proposal is similar in scope, I allocated some buffer time to address unexpected issues and provide thorough testing.
Timeline
[Before Coding Starts]
- May 4-8: Get to know mentor and discuss next steps.
- May 11-15: Take a closer look at
NameLookup.cpp and NameLookupRequests.cpp to better understand existing semantics and result caching behavior.
- May 18-22: Look at the compiler’s
NameLookup test directory for potential tests to include, and experiment with existing SwiftSyntax tests to become more familiar with the codebase.
[Coding Starts]
- May 25-29: Set up the qualified lookup API outlined above, write tests for
QualifiedLookupResult.members and .implicitMembers; extend unqualified lookup’s testing infrastructure.
- June 1-5: Implement qualified lookup for nominal types without a symbol table or configuration; check results using initial tests and add more tests for corner cases.
- June 8-12: Extend implementation to protocols and extensions; add
.conditionalMembers results; test more edge-cases.
- June 15-19: Set up SymbolTable API and add infrastructure for testing
#if and .lookForSupertypes results.
- June 22-26: Implement SymbolTable API and test; add test cases for
.lookForMacros.
- June 29 - July 3: Implement the aforementioned
.lookupForMacros and .lookForSupertypes results; miscellaneous bug fixes.
[Midterm Evaluation]
- July 6-10: Incorporate feedback from midterm evaluation and update plan; clean up and document code.
- July 13-17: Add tests for and implement
.lookForDynamicMember.
- July 20-24: Integrate with existing unqualified lookup API and add integration tests.
- July 27-31: Allow time for unforeseen challenges.
- August 3-7: Add benchmarks and fix performance issues.
- August 10-14: Review code documentation and write documentation articles.
- August 17-21: Fix remaining bugs; integrate the updated SwiftLexicalLookup with existing codebase.
[Optional Extension]
- August 24 - November 2: Integrate with the compiler’s name lookup and testing infrastructure.
.