@samitouri / QOS-React
Code Commits Issues Pulls Sessions CI/CD
main
main
md 176 lines 7.51 KB
Rendered Raw
1 # inferReactiveScopeVariables
2
3 ## File
4 `src/ReactiveScopes/InferReactiveScopeVariables.ts`
5
6 ## Purpose
7 This is the **1st of 4 passes** that determine how to break a React function into discrete reactive scopes (independently memoizable units of code). Its specific responsibilities are:
8
9 1. **Identify operands that mutate together** - Variables that are mutated in the same instruction must be placed in the same reactive scope
10 2. **Assign a unique ReactiveScope to each group** - Each disjoint set of co-mutating identifiers gets assigned a unique ScopeId
11 3. **Compute the mutable range** - The scope's range is computed as the union of all member identifiers' mutable ranges
12
13 The pass does NOT determine which instructions compute each scope, only which variables belong together.
14
15 ## Input Invariants
16 - `InferMutationAliasingEffects` has run - Effects describe mutations, captures, and aliasing
17 - `InferMutationAliasingRanges` has run - Each identifier has a valid `mutableRange` property
18 - `InferReactivePlaces` has run - Places are marked as reactive or not
19 - `RewriteInstructionKindsBasedOnReassignment` has run - Let/Const properly determined
20 - All instructions have been numbered with valid `InstructionId` values
21 - Phi nodes are properly constructed at block join points
22
23 ## Output Guarantees
24 - Each identifier that is part of a mutable group has its `identifier.scope` property set to a `ReactiveScope` object
25 - All identifiers in the same scope share the same `ReactiveScope` reference
26 - The scope's `range` is the union (min start, max end) of all member mutable ranges
27 - The scope's `range` is validated to be within [1, maxInstruction+1]
28 - Identifiers that only have single-instruction lifetimes (read once) may not be assigned to a scope unless they allocate
29
30 ## Algorithm
31
32 ### Phase 1: Find Disjoint Mutable Values (`findDisjointMutableValues`)
33
34 Uses a Union-Find (Disjoint Set) data structure to group identifiers that mutate together:
35
36 1. **Handle Phi Nodes**: For each phi in each block:
37 - If the phi's result is mutated after creation (mutableRange.end > first instruction in block), union the phi with all its operands
38 - This ensures values that flow through control flow and are later mutated are grouped together
39
40 2. **Handle Instructions**: For each instruction:
41 - Collect mutable operands based on instruction type:
42 - If lvalue has extended mutable range OR instruction may allocate, include lvalue
43 - For StoreLocal/StoreContext: Include lvalue if it has extended mutable range, include value if mutable
44 - For Destructure: Include each pattern operand with extended range, include source if mutable
45 - For MethodCall: Include all mutable operands plus the computed property (to keep method resolution in same scope)
46 - For other instructions: Include all mutable operands
47 - Exclude global variables (mutableRange.start === 0) since they cannot be recreated
48 - Union all collected operands together
49
50 ### Phase 2: Assign Scopes
51
52 1. Iterate over all identifiers in the disjoint set using `forEach(item, groupIdentifier)`
53 2. For each unique group, create a new ReactiveScope:
54 - Generate a unique ScopeId from the environment
55 - Initialize range from the first member's mutableRange
56 - Set up empty dependencies, declarations, reassignments sets
57 3. For subsequent members of the same group:
58 - Expand the scope's range to encompass the member's mutableRange
59 - Merge source locations
60 4. Assign the scope to each identifier: `identifier.scope = scope`
61 5. Update each identifier's mutableRange to match the scope's range
62
63 **Validation**: After scope assignment, validate that all scopes have valid ranges within [1, maxInstruction+1].
64
65 ## Key Data Structures
66
67 ### DisjointSet<Identifier>
68 A Union-Find data structure optimized for grouping items into disjoint sets:
69
70 ```typescript
71 class DisjointSet<T> {
72 #entries: Map<T, T>; // Maps each item to its parent (root points to self)
73
74 union(items: Array<T>): void; // Merge items into one set
75 find(item: T): T | null; // Find the root of item's set (with path compression)
76 forEach(fn: (item, group) => void): void; // Iterate all items with their group root
77 }
78 ```
79
80 Path compression is used during `find()` to flatten the tree structure, improving subsequent lookup performance.
81
82 ### ReactiveScope
83 ```typescript
84 type ReactiveScope = {
85 id: ScopeId;
86 range: MutableRange; // [start, end) instruction range
87 dependencies: Set<ReactiveScopeDependency>; // Inputs (populated later)
88 declarations: Map<IdentifierId, ReactiveScopeDeclaration>; // Outputs (populated later)
89 reassignments: Set<Identifier>; // Reassigned variables (populated later)
90 earlyReturnValue: {...} | null; // For scopes with early returns
91 merged: Set<ScopeId>; // IDs of scopes merged into this one
92 loc: SourceLocation;
93 };
94 ```
95
96 ## Edge Cases
97
98 ### Global Variables
99 Excluded from scopes (mutableRange.start === 0) since they cannot be recreated during memoization.
100
101 ### Phi Nodes After Mutation
102 When a phi's result is mutated after the join point, all phi operands must be in the same scope to ensure the mutation can be recomputed correctly.
103
104 ### MethodCall Property Resolution
105 The computed property load for a method call is explicitly added to the same scope as the call itself.
106
107 ### Allocating Instructions
108 Instructions that allocate (Array, Object, JSX, etc.) add their lvalue to the scope even if the lvalue has a single-instruction range.
109
110 ### Single-Instruction Ranges
111 Values with range `[n, n+1)` (used exactly once) are only included if they allocate, otherwise they're just read.
112
113 ### enableForest Config
114 When enabled, phi operands are unconditionally unioned with the phi result (even without mutation after the phi).
115
116 ## TODOs
117 1. `// TODO: improve handling of module-scoped variables and globals` - The current approach excludes globals entirely, but a more nuanced handling could be beneficial.
118
119 2. Known issue with aliasing and mutable lifetimes (from header comments):
120 ```javascript
121 let x = {};
122 let y = [];
123 x.y = y; // RHS is not considered mutable here bc not further mutation
124 mutate(x); // bc y is aliased here, it should still be considered mutable above
125 ```
126 This suggests the pass may miss some co-mutation relationships when aliasing is involved.
127
128 ## Example
129
130 ### Fixture: `reactive-scope-grouping.js`
131
132 **Input:**
133 ```javascript
134 function foo() {
135 let x = {};
136 let y = [];
137 let z = {};
138 y.push(z); // y and z co-mutate (z captured into y)
139 x.y = y; // x and y co-mutate (y captured into x)
140 return x;
141 }
142 ```
143
144 **After InferReactiveScopeVariables:**
145 ```
146 [1] mutate? $19_@0[1:14] = Object { } // x's initial object, scope @0
147 [2] store $21_@0[1:14] = StoreLocal x // x in scope @0
148 [3] mutate? $22_@1[3:11] = Array [] // y's array, scope @1
149 [4] store $24_@1[3:11] = StoreLocal y // y in scope @1
150 [5] mutate? $25_@2 = Object { } // z's object, scope @2
151 [10] MethodCall y.push(z) // Mutates y, captures z
152 [13] PropertyStore x.y = y // Mutates x, captures y
153 ```
154
155 The `y.push(z)` joins y and z into scope @1, and `x.y = y` joins x and y into scope @0. Because y is now in @0, and z was captured into y, ultimately x, y, and z all end up in the same scope @0.
156
157 **Compiled Output:**
158 ```javascript
159 function foo() {
160 const $ = _c(1);
161 let x;
162 if ($[0] === Symbol.for("react.memo_cache_sentinel")) {
163 x = {};
164 const y = [];
165 const z = {};
166 y.push(z);
167 x.y = y;
168 $[0] = x;
169 } else {
170 x = $[0];
171 }
172 return x;
173 }
174 ```
175
176 All three objects (x, y, z) are created within the same memoization block because they co-mutate and could potentially alias each other.