RyanCavanaugh
commented
1 year ago I'm not sure this is quite feasible. The results computed from symbol links and node links do not necessarily have the same meaning in a future program that has edits, even if those edits are outside the current file.
The other problem is that most of these node links and symbol links are not actually very computationally intensive. So in an interactive scenario, which is the only place you could do incremental updates, the amount of work being done here is actually quite minimal.
We could take a PR to examine it and see if there are meaningful gains, but I don't expect to be able to find much here.
yf-yang
jakebailey
This suggestion has the same settings with and is on top of #54222 : Language server, assuming only few characters are modified and others are remaining untouched. With incremental parser and some additional flags, we are able to distinguish "clean area" and "dirty area" of nodes. With incremental binding, there exists clean and dirty symbols (we are not able to distinguish them yet).
Semantic analysis are performed by the type checker lazily, after they are computed, intermediate or final results are cached by nodeLinks/symbolLinks. Each node/symbol has their own cache, but the caches are actually stored program-wide, nodes/symbols need to query their own by their id.
Whenever a change occurs, type checker applies an aggresive strategy: it assumes all the caches are outdated and recreates nodeLinks and symbolLinks, and we can actually reuse some of them.
The core step of semantic analysis is resolution, which refers to the computation needed to build the connection of a variable reference node and its symbol (declaration). Some cache needs multiple resolution steps (For example, get properties of a deep inherited class). After resolution, some computation is performed to get a type or other stuff. I'll start with those caches that involves one resolution step. Also, when considering performance, I'd like to ignore the overhead of resolution between two files, just theoratically describe what procedure could be bypassed, in order to reduce factors got involved.
Reuse one step resolution
There are four scenarios:
undefined, then lazy computation is performed if needed. Memory leak now becomes a problem, because we no longer clear nodeLinks/symbolLinks.weakMapcould be a possible workaround.Now we have a problem: how to tell if the node/symbol is dirty or clean? Dirty nodes/symbols are detached from new AST/symbol tables, we do not have a chance to visit them, but they are not released by those caches.
Here I offer one possible implementation: use file version. Each node/symbol would have a "version" member. During incremental parsing phase, initialize/refresh version members of each node to the latest, incremental parsing stage is similar. Note that the dirty flag I mentioned in #54222 could be removed. Then, in type checker, when it finds a cache is available, compare its version to the file version.
I am not sure if it is easy to implement, because it means each cache entry access (specifically, each key access in xxlinks) needs to be modified. As far as I know, they should be updated one by one because there are tons of code patterns. Anyway, I'm theoretically discussing the idea here.
What about multi-step resolution
If we want to reuse multi-step resolution cache, then we need to store more information about the chain in the node containing the cache, which may not be a good idea. Even a simpler example that a node points to a type with one step resolution is not viable, because we can't tag the version of the cached type.
However, for those scenarios, I'd like to compare them with our baseline, the existing strategy: clear everything, recompute anything when you need it. Suppose for these scenarios, we just choose to recompute it, we can still reuse those one-step resolutions, which is better than reusing nothing at least.
Therefore, the complete suggestion is: identify those cache entry that both cache holder and cached target could be simply versioned (For example,
NodeLinks.resolvedSymboland try to reuse them. For others, we can still keep the same strategy.Tradeoff of memory usage
Note that dirty cached target is not released until type checker visits it again, so it may introduces higher memory usage. However, I think the tradeoff is minor, because we can have other strategies, such as performing a nodeLink/symbolLink scan every 200 versions and removing stale nodes/symbols.
Maybe starting from files
The idea is not complicated, but the codebase is, so I'd suggest an alternative:
We can start from reusing nodeLinks/symbolLinks between clean files. Files not get binded are indentified as "clean area" and rebinded files are "dirty area", for such granularity, it is already there.