google / google/closure-compiler
Simplify LinkedFlowScope
- Dominant language
- JavaScript
- Stars
- 7.7k
- Forks
- 1.2k
- Avg merge
- 2d 12h
- Merged PRs (30d)
- 6
Description
`LinkedFlowScope` currently uses a complicated combination of linked lists with ad hoc caching. At every control flow join point, we end up iterating over all elements in the flow scope and joining them all (even when joining may not be necessary) into a brand new map for the cache. This is potentially very expensive.
This structure could be greatly simplified by removing the cache and instead relying on persistent data structures to do the heavy lifting. Together with ES6 block scoping, we could potentially realize a significant performance improvement, in addition to fixing (or at least allowing us to fix) some existing known issues that are infeasible to deal with in the presence of this ad hoc caching.
I propose the following.
1. Procure a `PersistentMap` type that can use `Comparable` keys.
2. Replace `LinkedFlowScope`'s `lastSlot` and `cache` fields with a `PersistentMap>`.
3. `FlowSlot` contains a `final PersistentMap` for storing properties, in addition to the normal `StaticTypedSlot` fields.
4. `TypedScope` uses an ordering based on `getDepth()`, with a `checkState` that any compared scopes with the same depth are identical.
This would allow the following:
1. When exiting a scope, pop off the entire flow map from that scope. This solves the bug documented by e4798477 since every separate inference traversal through a loop will get its own fresh scope with brand new lexical variables (both qualified and simple).
2. When assigning to a name (qualified or simple) we can invalidate all specialization on all properties by updating its `FlowSlot` with an empty property map (cf. #2854).
3. When joining flow scopes, any scopes whose specialization is the same can be joined trivially by copying a single reference. The same can occur for some unmodified subtrees within a scope.
4. It may be possible to actually make `FlowScope` shallowly immutable. This would do away with the need for `createChildFlowScope`, `optimize`, and `isFrozen`, which would be a further simplification.
Contributor guide
Assessment
This issue has not been assessed yet.