Qualified Lookup in SwiftLexicalLookup

[filip-sakel]

It’s been a while since my last post, so I thought I’d share a quick update. First, the initial PR landed, and the second PR is ready for review. The first PR implements the foundation of qualified lookup as discussed in the previous posts: it allows users to search for members of a DeclGroupSyntax (nominal-type or extension declaration), filtering for specific declarations with a DeclNameReference (formerly DeclNameRef), in order to return a ValueDeclSyntax (previously ValueDecl). I’ll create an official RFC once the whole qualified-lookup API stabilizes. So what’s the remaining API?

Structural Type Resolution

If you recall from my last post, to validate qualified lookup against the compiler, we want to hook into this call:

/// Looks for given `member` name in the given `Type`.
bool lookupQualified(Type type, DeclNameRef member,
                     SourceLoc loc, NLOptions options,
                     SmallVectorImpl<ValueDecl *> &decls) const;

Here, Type is similar to swift-syntax’s TypeSyntax, but keen observers will notice that TypeSyntax doesn’t provide us with any information on which types the given syntax refers to and what their extensions are. This is where structural resolution comes in (which is what I’ve been working on for the last month ).

Structural Resolution

A type syntax can resolve to many different types, including nominal types, compositions, functions, tuples, metatypes, etc. Specifically, when I'm talking about resolving nominal types, I mean finding the nominal-type declaration where they are defined and, optionally, their extensions.

The most interesting example IMO is a member type of the form A.B.C.[...].F. According to Compiling Swift Generics, in this example, we would start by performing unqualified lookup to find the leaf type A, and issue a qualified type lookup for B, then C, and so on until we reach F. Throughout this process, if we encounter a type alias, we recursively resolve the aliased type. Moreover, we stop at generic parameters and associated types because they’re out of scope for this project (and the compiler does the same at this stage).

Taking a step back, you'll notice that we're juggling a lot of state with all these unqualified/qualified requests and recursive type-alias resolution. So, to make sure we don't get stuck in a loop, my current prototype centralizes this state in a single TypeQualifier struct that treats each step of the lookup as a separate request and that catches cycles like circular type-aliases, e.g.:

typealias A = B
typealias B = A

For anyone interested, here’s a more detailed explanation of the stages of lookup.

The last big piece of the structural-resolution puzzle is finding a nominal-type declaration's extensions.

Extension Binding

Extension binding is the process of associating an extension declaration with the type it extends. This process is necessary to properly locate type members. Here’s an example:

struct A {}
typealias B = A
extension B { struct C {} } // `extension B` "binds" to `struct A`

func f(_: A.C) {} // <- Look up `A.C` here

Suppose we’re looking up A.C. We observe that A refers to struct A , so we start looking for a type member named C. If we don’t bind all accessible extensions first and only look in the main declaration struct A {}, we won’t find C. Hence, we need to bind the available extensions before performing qualified lookup.

Challenges

Unfortunately for me, extension binding is intricate. The complexity boils down to the fact that in Swift, we can form type aliases, and we can extend types introduced in other extensions; consequently:

1. Type aliases make searching for extensions a global problem. We can’t simply search for extension A. Instead, we have to bind all extensions accessible from the type syntax A.C to determine which extensions actually bind to A.
2. Having extensions of member types introduced in other extensions means extensions can depend on other extensions. This constraint requires that extension binding be incremental: we bind one extension at a time, updating our dependency graph, and invalidating old results. You can think of incremental binding as hiding all extensions from SwiftLexicalLookup and slowly revealing one extension at a time.

It's worth expanding on our incremental binding approach, so consider the following program:

struct A {}
extension A.Outer { struct B {} }
extension A { typealias Outer = A }

func f(_: A.B) // <- Look up A.B

Here are the detailed steps to resolve A.B:

• We find struct A and start extension-binding before looking for .B. As far as type resolution is concerned, the type-resolution state currently sees the struct A declaration without any extensions.
• So, we introduce extension A.Outer, which resolves to an error since struct A doesn’t have a type member Outer. Importantly, we record the fact that the resolution result of extension A.Outer depends on the type member Outer.
• Then, we reveal extension A to the type resolver, which introduces a type member Outer. Based on the dependency we recorded before, we invalidate extension A.Outer, by removing it from the type-resolution state.
• Finally, we can reattempt extension A.Outer. Now that the type resolver is considering both struct A and extension A, we can indeed find typealias Outer = A, and bind extension A.Outer to struct A.
• With extension binding complete, we resolve A.B to struct B {}.

Phew, that was a lot. However, the point I want to drive home is that we can recursively resolve an extension, bind another extension that invalidates the first, and re-resolve the original extension.

Another important issue is that extension binding, similar to other systems using dependency graphs, may run into cycles. However, seeing that this post is getting too long, I’ll cover cycle diagnostics and language constraints in a future post.