Swift type resolution algorithm?

can someone point me toward an algorithm that can determine what type symbol (including generic parameters and associated types) a Swift type identifier expression points to?

for example, if i have the following declarations:

protocol Extendable:SIMD 
{
    associatedtype Extended 
        where Extended:SIMD, Extended.Scalar == Scalar
} 
struct Vector<Storage, T> 
    where Storage:SIMD, T:SIMDScalar, Storage.Scalar == T
{
}

extension Vector where Storage:Extendable 
{
    struct Plane
    {
    }
}

extension Vector.Plane 
{
    func method() -> Storage.Extended 
}

i want to be able to resolve Storage.Extended to the associatedtype Extendable.Extended, with respect to the Vector.Plane.method() declaration.

the algorithm i currently have looks like this (simplified for clarity):

let path:ArraySlice<String> 
var next:Node?
if symbol.first == "Self" 
{
    switch self.kind 
    {
    case .enum, .struct, .class, .protocol, .extension: 
        // `Self` refers to this node, and all its extensions 
        next    = self 
    default:
        // `Self` refers to the parent node, and all its extensions 
        guard let parent:InternalNode = self.parent 
        else 
        {
            print(warning)
            return nil 
        }
        next    = parent 
    }
    path = symbol.dropFirst()
}
else 
{
    next = self
    path = symbol[...]
}
// this loop searches in the next outer scope
higher:
while let node:Node = next  
{
    defer 
    {
        next = node.parent 
    }
    
    var keys:ArraySlice<String> = path
    var candidates:[Node]       = self
    var search:[[Node]]         = 
        < all of the typealiases, and protocols the current node conforms to >
    var matched:[String]        = []
    matching:
    while let key:String = keys.popFirst() 
    {
        matched.append(key)
// search in the symbol itself, then typealiases, then conformances
        for phase:[Node] in search
        {
            for node:Node in phase 
            {
// we need to search through all outer scopes for generic 
// parameters, *before* looking through any inheritances
                var next:Node? = node
                while let node:Node  = next 
                {
// see if this node has a generic parameter named 'key', and 
// get the protocols it conforms to, from the `where` constraints
// on this node. ignores `where` constraints whose subject 
// isn’t a generic in this node 
                    if let inclusions:Inclusions   = node.generics[key]
                    {
                        candidates  = [node]
// find out what else we know about this generic. for example,
// if we have "where Foo.Bar:P", and `matched` is ["Foo", "Bar"], 
// we’ll retrieve the "P" protocol
                        if let context:Inclusions  = self.context[matched]
                        {
                            search  = node.search(space: [inclusions, context])
                        }
                        else 
                        {
                            search  = node.search(space: [inclusions])
                        }
                        continue matching
                    }
                    
                    next = node.parent
                }
            }
            
            for node:Node in phase 
            {
                if let next:Node = node.children[key]
                {
                    candidates  = [next] 
                    search      = 
    < all of the typealiases, and protocols the `next` node conforms to >
                    continue matching 
                }
            }
        }
        if path.count < symbol.count 
        {
// path was relative (because we removed "Self"), do not escalate 
            break higher 
        }
        else 
        {
// look in the next-higher scope
            continue higher
        }
    }
...

i found that it works for ~98% of situations, but it isn’t able to handle more sophisticated type expressions, like those with lots of typealiases, or complicated type constraints. It doesn’t work for the example above, since it doesn’t know that because method() is scoped to Vector.Plane, that Storage is Extendable, and not just SIMD (from where the generic parameter was originally declared).

The algorithm I have is already a collection of hacks i’ve added over time to cover various failing cases, and there’s a good chance the more hacks I introduce, the greater the chance it’s going to start finding symbols it shouldn’t be finding. what’s the correct solution here?

I don't think there's a simple description of this, apart from a not-very-helpful one of "whatever is currently implemented". Maybe @Slava_Pestov or @codafi have ideas?

(Also, is the question deliberately "how do I implement this" or is it more results-focused where using some SourceKit APIs would be good enough?)

1 Like

Unfortunately, the question is ‘how do i implement this”, as i’ve found the output of dump-symbol-graph to be insufficient for my use case, which is generating richly-linked API reference pages with “smart” code snippets (code snippets where types are linked to appropriate library and standard library symbols.) For example, default protocol requirement implementations (example) require resolving types in where clauses that aren’t actually present in the requirement-symbol itself.

you can see an example of a generated reference page here: Godot.List - Godot Swift Documentation

and a failing example here: VectorRangeExpression.Bound - Godot Swift Documentation
(the T and Storage symbols are being resolved to generic parameters on the typealias target, instead of the correct associated types from the surrounding scope)

i haven’t looked at sourcekit APIs in too much detail, but the tool that i’m building currently does use SwiftSyntax to highlight code snippets.

Terms of Service

Privacy Policy

Cookie Policy