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?
