Support find-all-references (better)

[hendrikvanantwerpen]

Context

Finding all references to a definition is often useful. However, this is not as simple as doing backward path stitching. To see why consider the following example:

interface Foo {
    bar() Foo
    quz() Foo // <-- find references to this definition
}

function test(foo: Foo) {
    foo/* any number of .bar() calls */.quz()
}

If we were to try stitching partial paths backwards from the quz definition, we'd have to speculate on the number of calls to bar that may precede the call to quz. This means the search space is unbounded.

The alternative we have been using is to start from all references with the same name as the definition, and do forward path stitching to check if they resolve to the desired definition. This works, and keeps the search space limited.

Problem

Sometimes we are also interested in aliases that resolve to the desired definition. For example, if a name is renamed as part of an import (e.g., import { foo as baz } from ...), we want to be able to find bar as well as foo.

Improved approach

Use the original approach, starting from references with the same name as the definition, but compute a fixed point using an additional set of alias paths. Alias paths are paths from a definition to a reference (probably with empty pre/postconditions).

Initially, start with the desired definition. Find all references among the references with the same name that reach the definition. For the resulting set of references, lookup alias paths ending in the reference, and repeat the search for the alias definitions that we haven't seen before.

Implementation

A database of alias paths needs to be computed, and should support efficient lookup based on the final reference node.

One problem is that we might do duplicate work. Consider [ref foo] -> [def foo] -> [ref bar] -> [def bar]: when looking for references to bar, when looking for references to foo, the path stitching would find the path to the [ref foo] -> [def foo] but then keep extending it via [ref bar] to [def bar], redoing work we already did in an earlier iteration. We would need better control over which paths are extended in the next stitching phase (the current predicate is a bit of a hack and doesn't fit the stitch and inspect results later approach), or have better caching so we can reuse the work from a previous phase without redoing it. The latter might in general be a good improvement to path stitching!