@samitouri / QOS-React-1
Code Commits Issues Pulls Sessions CI/CD
main
main
md 134 lines 5.93 KB
Rendered Raw
1 # mergeOverlappingReactiveScopesHIR
2
3 ## File
4 `src/HIR/MergeOverlappingReactiveScopesHIR.ts`
5
6 ## Purpose
7 This pass ensures that reactive scope ranges form valid, non-overlapping blocks in the output JavaScript program. It merges reactive scopes that would otherwise be inconsistent with each other due to:
8
9 1. **Overlapping ranges**: Scopes whose instruction ranges partially overlap (not disjoint and not nested) must be merged because the compiler cannot produce valid `if-else` memo blocks for overlapping scopes.
10
11 2. **Cross-scope mutations**: When an instruction within one scope mutates a value belonging to a different (outer) scope, those scopes must be merged to maintain correctness.
12
13 The pass guarantees that after execution, any two reactive scopes are either:
14 - Entirely disjoint (no common instructions)
15 - Properly nested (one scope is completely contained within the other)
16
17 ## Input Invariants
18 - Reactive scope variables have been inferred (`InferReactiveScopeVariables` pass has run)
19 - Scopes have been aligned to block scopes (`AlignReactiveScopesToBlockScopesHIR` pass has run)
20 - Each `Place` may have an associated `ReactiveScope` with a `range` (start/end instruction IDs)
21 - Scopes may still have overlapping ranges or contain instructions that mutate outer scopes
22
23 ## Output Guarantees
24 - **No overlapping scopes**: All reactive scopes either are disjoint or properly nested
25 - **Consistent mutation boundaries**: Instructions only mutate their "active" scope (the innermost containing scope)
26 - **Merged scope ranges**: Merged scopes have their ranges extended to cover the union of all constituent scopes
27 - **Updated references**: All `Place` references have their `identifier.scope` updated to point to the merged scope
28
29 ## Algorithm
30
31 ### Phase 1: Collect Scope Information (`collectScopeInfo`)
32 - Iterates through all instructions and terminals in the function
33 - Records for each `Place`:
34 - The scope it belongs to (`placeScopes` map)
35 - When scopes start and end (`scopeStarts` and `scopeEnds` arrays, sorted in descending order by ID)
36 - Only records scopes with non-empty ranges (`range.start !== range.end`)
37
38 ### Phase 2: Detect Overlapping Scopes (`getOverlappingReactiveScopes`)
39 Uses a stack-based traversal to track "active" scopes at each instruction:
40
41 1. **For each instruction/terminal**:
42 - **Handle scope endings**: Pop completed scopes from the active stack. If a scope ends while other scopes that started later are still active (detected by finding the scope is not at the top of the stack), those scopes overlap and must be merged via `DisjointSet.union()`.
43
44 - **Handle scope starts**: Push new scopes onto the active stack (sorted by end time descending so earlier-ending scopes are at the top). Merge any scopes that have identical start/end ranges.
45
46 - **Handle mutations**: For each operand/lvalue, if it:
47 - Has an associated scope
48 - Is mutable at the current instruction
49 - The scope is active but not at the top of the stack (i.e., an outer scope)
50
51 Then merge all scopes from the mutated outer scope to the top of the stack.
52
53 2. **Special case**: Primitive operands in `FunctionExpression` and `ObjectMethod` are skipped.
54
55 ### Phase 3: Merge Scopes and Rewrite References
56 1. For each scope in the disjoint set, compute the merged range as the union (min start, max end)
57 2. Update all `Place.identifier.scope` references to point to the merged "group" scope
58
59 ## Key Data Structures
60
61 ### ScopeInfo
62 ```typescript
63 type ScopeInfo = {
64 scopeStarts: Array<{id: InstructionId; scopes: Set<ReactiveScope>}>;
65 scopeEnds: Array<{id: InstructionId; scopes: Set<ReactiveScope>}>;
66 placeScopes: Map<Place, ReactiveScope>;
67 };
68 ```
69
70 ### TraversalState
71 ```typescript
72 type TraversalState = {
73 joined: DisjointSet<ReactiveScope>; // Union-find for merged scopes
74 activeScopes: Array<ReactiveScope>; // Stack of currently active scopes
75 };
76 ```
77
78 ### DisjointSet<ReactiveScope>
79 A union-find data structure that tracks which scopes should be merged into the same group.
80
81 ## Edge Cases
82
83 ### Identical Scope Ranges
84 When multiple scopes have the exact same start and end, they are automatically merged since they would produce the same reactive block.
85
86 ### Empty Scopes
87 Scopes where `range.start === range.end` are skipped entirely.
88
89 ### Primitive Captures in Functions
90 When a `FunctionExpression` or `ObjectMethod` captures a primitive operand, it's excluded from scope merging analysis.
91
92 ### JSX Single-Instruction Scopes
93 The comment in the code notes this isn't perfect - mutating scopes may get merged with JSX single-instruction scopes.
94
95 ### Non-Mutating Captures
96 The pass records both mutating and non-mutating scopes to handle cases where still-mutating values are aliased by inner scopes.
97
98 ## TODOs
99 From the comments in the source file, the design constraints arise from the current compiler output design:
100 - **Instruction ordering is preserved**: If reordering were allowed, disjoint ranges could be produced by reordering mutating instructions
101 - **One if-else block per scope**: The current design doesn't allow composing a reactive scope from disconnected instruction ranges
102
103 ## Example
104
105 ### Fixture: `overlapping-scopes-interleaved.js`
106
107 **Input Code:**
108 ```javascript
109 function foo(a, b) {
110 let x = [];
111 let y = [];
112 x.push(a);
113 y.push(b);
114 }
115 ```
116
117 **Before MergeOverlappingReactiveScopesHIR:**
118 ```
119 [1] $20_@0[1:9] = Array [] // x belongs to scope @0, range [1:9]
120 [2] x$21_@0[1:9] = StoreLocal...
121 [3] $23_@1[3:13] = Array [] // y belongs to scope @1, range [3:13]
122 [4] y$24_@1[3:13] = StoreLocal...
123 ```
124 Scopes @0 [1:9] and @1 [3:13] overlap: @0 starts at 1, @1 starts at 3, @0 ends at 9, @1 ends at 13. This is invalid.
125
126 **After MergeOverlappingReactiveScopesHIR:**
127 ```
128 [1] $20_@0[1:13] = Array [] // Merged scope @0, range [1:13]
129 [2] x$21_@0[1:13] = StoreLocal...
130 [3] $23_@0[1:13] = Array [] // Now also scope @0
131 [4] y$24_@0[1:13] = StoreLocal...
132 ```
133
134 Both `x` and `y` now belong to the same merged scope @0 with range [1:13], producing a single `if-else` memo block in the output.