Currently, our invalidation/incremental computation algorithm has a few flaws. It has many special cases, which hints that we have not arrived at the correct generalization of the problem, which can be described as "determining the smallest sub-graph that needs to be recomputed when changes occur".
There are also two main performance issues:
- We don't skip unnecessary work effectively. For example, if a local variable is introduced, there's no reason to run resolution
- We traverse and invalidate the graph on every document changed. This is highly wasteful because traversing the graph is expensive and because a modification to another document may influence the amount of work we have to do. For example, if we process one document change, we may conclude that a declaration has to be removed. If a second change is immediately consumed that would keep the declaration alive, we now need to re-create it
There are already well established algorithms for incremental computation in graphs, but in essence we need something that looks like this:
- Consuming a document change updates the indexing-level information (definitions, references...) and remembers in the
Graph the document diff. That means, which meaningful changes happened between the old and new versions of document. If two definitions are identical, they should not appear in the document diff and should not be accumulated as pending work
- After all document changes were consumed, when
resolve is triggered, the first step is to use the pending work to invalidate the smallest sub-graph possible. This guarantees that we're taking all document changes into account to avoid getting into a situation like the one described in 2, where changes influence each other and impact the final result
- We need to skip work as much as possible. When invalidation is triggered inside of resolution, it will basically enqueue units into the queue. We should not enqueue unnecessary work, such as adding an
Ancestor unit if no direct ancestors were modified
- Our solution needs to be a straight forward algorithm, similar to the resolution approach. We need to determine, what are the primitives that determine invalidation? Sometimes, it's a
StringId (if a new constant is defined that may impact the resolution of previously computed references), a DeclarationId that then invalidates all of its members (if the fully qualified name got invalidated because of constant resolution) or a DeclarationId for ancestor linearization (which may trigger even more invalidation)
Note: one interesting intersection is that the document diff may also be reused by #957 to determine the smallest amount of database updates we have to perform.
Currently, our invalidation/incremental computation algorithm has a few flaws. It has many special cases, which hints that we have not arrived at the correct generalization of the problem, which can be described as "determining the smallest sub-graph that needs to be recomputed when changes occur".
There are also two main performance issues:
There are already well established algorithms for incremental computation in graphs, but in essence we need something that looks like this:
Graphthe document diff. That means, which meaningful changes happened between the old and new versions of document. If two definitions are identical, they should not appear in the document diff and should not be accumulated as pending workresolveis triggered, the first step is to use the pending work to invalidate the smallest sub-graph possible. This guarantees that we're taking all document changes into account to avoid getting into a situation like the one described in 2, where changes influence each other and impact the final resultAncestorunit if no direct ancestors were modifiedStringId(if a new constant is defined that may impact the resolution of previously computed references), aDeclarationIdthat then invalidates all of its members (if the fully qualified name got invalidated because of constant resolution) or aDeclarationIdfor ancestor linearization (which may trigger even more invalidation)Note: one interesting intersection is that the document diff may also be reused by #957 to determine the smallest amount of database updates we have to perform.