Support consuming document changes incrementally

[vinistock]

We're getting close to the design of the resolution phase working properly and now a new problem arises: we are only able to take all of the information we indexed and transform it in one go, but we have no way of accounting for incremental changes.

To support usage in LSP mode (and in the future, incremental mode through the database), we need to be able to consume changes incrementally.

As part of this issue, let's understand how we can implement this.

Notes

The unit of indexing or consuming changes is always the same: a document. The incremental aspect comes from understanding what kind of change happened and matching that to what needs to happen in the subsequent parts of the analysis.

Some examples:

• If someone just adds a bunch of blank lines in a file, we need to index it again (to update the offsets), but there's no need to discard declaration level information or run resolution again
• If someone adds new declarations that don't impact constant and ancestor resolution (like a new method), maybe we can skip most of the resolution phase
• If someone deletes a constant or changes inheritance, we need to try to compute the minimum amount of work that has to happen to account for it

My understanding is that most type checkers use hashed values for this. For example, if we hash all definitions that we got in a local graph from indexing a single document and that doesn't match the previous state, then there are new/modified definitions (maybe we need to remember the definition hashes in Document?). Maybe we need an ancestors hash?

[thomasmarshall]

I've been exploring this and trying to understand what changes we would need to make based on your examples and suggestions. I've been using Claude to help me navigate the codebase and come up with a plan for how we could implement this. I think it's something like this:

During resolution:

• Add hash fields to Document
  • definitions_hash comprising class/module/constant names and nesting
  • ancestors_hash comprising superclass and mixins
• Track dependencies between documents and declarations so we know which declarations each document contributes towards

When a document changes:

• Compare the old hashes against new hashes to determine what kind of change happened
  • Offsets only (e.g. blank line added, or code changes unrelated to the "shape" of the definitions)
  • Definitions changed (e.g. constants/methods added/removed)
  • Ancestors changed (e.g. superclass/mixins added/removed)
• Process the graph depending on the kind of change that happened
  • For "offsets only" changes we don't need to do anything, leave the graph as-is
  • For definition changes we should invalidate any declarations the document contributed to (via the dependency tracking) and re-run resolution for them
  • For ancestor changes, I guess it's similar to definition changes but also invalidate descendants (not sure how this would work)?

I may need a bit of help and advice for that last part, but is the approach I've outlined above roughly what you had in mind?

[Morriar]

Track dependencies between documents and declarations so we know which declarations each document contributes towards

I think we can already do this through Document#definitions -> Grahp#definitions_to_declarations -> Declaration

[Morriar]

Maybe we can split the work into 2 steps:

1. First, let's implement the dumb way to do it: when we receive a change, let's invalidate everything and recompute. This will allow us to use the feature (even if slow).

2. Then, let's implement a smarter way to do it with minimum invalidation.

[thomasmarshall]

Yes, thanks @Morriar that's the plan—I had a pairing session with @vinistock earlier where we discussed the same thing 👍

[thomasmarshall]

I have opened two draft PRs demonstrating some different approaches:

• Prototype: Name-based invalidation for incremental updates #571
• Prototype: Fast/slow path for incremental updates #572

My initial explorations were unfortunately flat wrong:

• Add partial resolution #481
• Add partial resolution alternative #503

I also explored another dependency-tracking approach that (different to #571) which was geared towards more targeted/precise invalidation. Instead of tracking dependents on Name at index time, it would track "searches" during resolution—that is any namespace that we looked for a member with the same name, whether we found it or not. For example:

module Foo
  class Bar
    include Baz
  end
end

module Baz
  ABC = 123
end

class Qux < Foo::Bar
  puts ABC
end

The ABC reference name has nesting Qux. The lexical dependency tracking approach would record that the ABC name is a dependent of the Qux name. However, if we did search based dependency tracking during resolution we would know:

• Searched for ABC member in ::Qux class via lexical search
• Searched for ABC member in ::Foo::Bar class via ancestor search
• Found ABC member in ::Baz module via ancestor search

So the ABC name is a dependent of three namespaces: ::Qux, ::Foo::Bar, ::Baz.

This allows us to do much more precise invalidation. For example, when a member is added to, or removed from, a namespace, we can find anything that searched for that member name in that namespace.

However, this doesn't quite work, because tracking on namespaces requires being able to look at a local definition and determine which declaration it SHOULD correspond to (i.e. resolution).

[thomasmarshall]

I gathered together the test cases from my various other prototypes and pushed them to #571.

The three main approaches I tried:

Namespace (declaration) based invalidation

When a member is added to or removed from a namespace, we should only need to invalidate things that searched that namespace for that member. When an ancestor affecting change happens to a namespace, we should invalidate everything that searched that namespace (no filter here, because we can't easily know which names the ancestor change adds/removes). This is difficult for a bunch of reasons, but a significant difficulty was aliasing.

module Foo
end

A = Foo

class A::B
end

Sorbet doesn't support this. Theoretically, it should be able to determine every namespace declaration without doing resolution (i.e. the syntactic FQN always matches the generated declaration FQN). But Rubydex does support aliasing, which makes it more difficult (potentially impossible?) to determine which declaration a given definition is for without doing resolution (as mentioned in the previous message).

Name based invalidation

See #571 for a full explanation of this approach.

Fast/slow path

See #572 for this approach, but it could be combined with any of the others.

Difficulties

• Aliases make things difficult. I believe we only track in one direction (i.e. we can find the targets for an alias, but not the aliases for a target). If a definition changes something about a declaration, how do we find which aliases are impacted (in order to invalidate their dependencies)? If a new alias is added, how do we determine which declaration it impacts without resolving the new target?
• I found it a little tricky to navigate the split between indexing and resolution. For example, names are a product of indexing and their resolution status is a product of resolution, yet they are quite tightly linked together. For example, when we want to lookup a declaration for a definition, we do so by traversing resolved names. If we un-resolve a name as part of indexing one file, we cannot then traverse that name to lookup a declaration when invalidating something from the next file. I would like that indexing only affects indexing artifacts (definitions, references etc), and resolving affects resolution artifacts (declarations, resolved names).
• Related to above, we could consider accumulating index changes and then processing them in batch, instead of updating one document at a time. For name-based invalidation, it's quite likely that multiple files will invalidate many of the same names. Doing so should be pretty quick the second time around, but it feels incorrect to me. I would expect we process all changes at once.
• Making things performant without inflating the size of the index too much is challenging. For example, it would be nice to track unresolved references so we can always (or selectively?) re-enqueue them for resolution when there is in incremental update. The search-based dependency tracking does this naturally (i.e. if an unresolved name searched for Foo in Bar, we could selectively enqueue those names).
• Visibility into what has been invalidated is quite difficult. I added the "diff" functionality above to compare two graphs, but in cases where something is different, I found it hard to track down why. I suppose that's partly a lack of domain knowledge, and if someone more familiar with the problem space saw that an ancestor was partial in one graph and complete in another, it might be more obvious what the problem is.
• Testing is quite tricky too as real projects are vastly more complicated than 2 or 3 document test scenarios. I found it necessary to run the incremental_verify example in Prototype: Name-based invalidation for incremental updates #571 in order to get more representative complexity from real projects. Though that sits at the opposite end of the spectrum—a real project is so complex that it's very hard to pin down the issue (as above).