@samitouri / QOS-React
Code Commits Issues Pulls Sessions CI/CD
main
main
md 158 lines 5.85 KB
Rendered Raw
1 # flattenReactiveLoopsHIR
2
3 ## File
4 `src/ReactiveScopes/FlattenReactiveLoopsHIR.ts`
5
6 ## Purpose
7 This pass **prunes reactive scopes that are nested inside loops** (for, for-in, for-of, while, do-while). The compiler does not yet support memoization within loops because:
8
9 1. Loop iterations would require reconciliation across runs (similar to how `key` is used in JSX for lists)
10 2. There is no way to identify values across iterations
11 3. The current approach is to memoize *around* the loop rather than *within* it
12
13 When a reactive scope is found inside a loop body, the pass converts its terminal from `scope` to `pruned-scope`. A `pruned-scope` terminal is later treated specially during codegen - its instructions are emitted inline without any memoization guards.
14
15 ## Input Invariants
16 - The HIR has been through `buildReactiveScopeTerminalsHIR`, which creates `scope` terminal nodes for reactive scopes
17 - The HIR is in valid block form with proper terminal kinds
18 - The block ordering respects control flow (blocks are iterated in order, with loop fallthroughs appearing after loop bodies)
19
20 ## Output Guarantees
21 - All `scope` terminals that appear inside any loop body are converted to `pruned-scope` terminals
22 - Scopes outside of loops remain unchanged as `scope` terminals
23 - The structure of blocks is preserved; only the terminal kind is mutated
24 - The `pruned-scope` terminal retains all the same fields as `scope` (block, fallthrough, scope, id, loc)
25
26 ## Algorithm
27
28 The algorithm uses a **linear scan with a stack-based loop tracking** approach:
29
30 ```
31 1. Initialize an empty array `activeLoops` to track which loop(s) we are currently inside
32 2. For each block in the function body (in order):
33 a. Remove the current block ID from activeLoops (if present)
34 - This happens when we reach a loop's fallthrough block, exiting the loop
35 b. Examine the block's terminal:
36 - If it's a loop terminal (do-while, for, for-in, for-of, while):
37 Push the loop's fallthrough block ID onto activeLoops
38 - If it's a scope terminal AND activeLoops is non-empty:
39 Convert the terminal to pruned-scope (keeping all other fields)
40 - All other terminal kinds are ignored
41 ```
42
43 Key insight: The algorithm tracks when we "enter" a loop by pushing the fallthrough ID when encountering a loop terminal, and "exits" the loop when that fallthrough block is visited.
44
45 ## Key Data Structures
46
47 ### activeLoops: Array<BlockId>
48 A stack of block IDs representing loop fallthroughs. When non-empty, we are inside one or more nested loops.
49
50 ### PrunedScopeTerminal
51 ```typescript
52 export type PrunedScopeTerminal = {
53 kind: 'pruned-scope';
54 fallthrough: BlockId;
55 block: BlockId;
56 scope: ReactiveScope;
57 id: InstructionId;
58 loc: SourceLocation;
59 };
60 ```
61
62 ### retainWhere
63 Utility from utils.ts - an in-place array filter that removes elements not matching the predicate.
64
65 ## Edge Cases
66
67 ### Nested Loops
68 The algorithm handles nested loops correctly because `activeLoops` is an array that can contain multiple fallthrough IDs. A scope deep inside multiple nested loops will still be pruned.
69
70 ### Scope Spanning the Loop
71 If a scope terminal appears before the loop terminal but its body contains the loop, it is NOT pruned because the scope terminal itself is not inside the loop.
72
73 ### Multiple Loops in Sequence
74 When exiting one loop (reaching its fallthrough) and entering another, `activeLoops` correctly clears the first loop before potentially adding the second.
75
76 ### Control Flow That Exits Loops (break/return)
77 The algorithm relies on block ordering and fallthrough IDs. Early exits via break/return don't affect the tracking since we track by fallthrough block ID.
78
79 ## TODOs
80 No explicit TODOs in this file. However, the docstring mentions future improvements:
81 > "Eventually we may integrate more deeply into the runtime so that we can do a single level of reconciliation"
82
83 This suggests a potential future feature to support memoization within loops via runtime integration.
84
85 ## Example
86
87 ### Fixture: `repro-memoize-for-of-collection-when-loop-body-returns.js`
88
89 **Input:**
90 ```javascript
91 function useHook(nodeID, condition) {
92 const graph = useContext(GraphContext);
93 const node = nodeID != null ? graph[nodeID] : null;
94
95 for (const key of Object.keys(node?.fields ?? {})) {
96 if (condition) {
97 return new Class(node.fields?.[field]); // <-- Scope @4 is here
98 }
99 }
100 return new Class(); // <-- Scope @5 is here (outside loop)
101 }
102 ```
103
104 **Before FlattenReactiveLoopsHIR:**
105 ```
106 [45] Scope scope @3 [45:72] ... block=bb35 fallthrough=bb36
107 bb35:
108 [46] ForOf init=bb6 test=bb7 loop=bb8 fallthrough=bb5
109 ...
110 [66] Scope scope @4 [66:69] ... block=bb37 fallthrough=bb38 <-- Inside loop
111 ...
112 [73] Scope scope @5 [73:76] ... block=bb39 fallthrough=bb40 <-- Outside loop
113 ```
114
115 **After FlattenReactiveLoopsHIR:**
116 ```
117 [45] Scope scope @3 [45:72] ... block=bb35 fallthrough=bb36 <-- Unchanged
118 ...
119 [66] <pruned> Scope scope @4 [66:69] ... block=bb37 fallthrough=bb38 <-- PRUNED!
120 ...
121 [73] Scope scope @5 [73:76] ... block=bb39 fallthrough=bb40 <-- Unchanged
122 ```
123
124 **Final Codegen Result:**
125 ```javascript
126 function useHook(nodeID, condition) {
127 const $ = _c(7);
128 // ... memoized Object.keys call (scope @2)
129
130 let t1;
131 if ($[2] !== condition || $[3] !== node || $[4] !== t0) {
132 // Scope @3 wraps the loop
133 t1 = Symbol.for("react.early_return_sentinel");
134 bb0: for (const key of t0) {
135 if (condition) {
136 t1 = new Class(node.fields?.[field]); // Scope @4 was PRUNED - no memoization
137 break bb0;
138 }
139 }
140 $[2] = condition;
141 $[3] = node;
142 $[4] = t0;
143 $[5] = t1;
144 } else {
145 t1 = $[5];
146 }
147 // ...
148
149 // Scope @5 - memoized (sentinel check)
150 if ($[6] === Symbol.for("react.memo_cache_sentinel")) {
151 t2 = new Class();
152 $[6] = t2;
153 }
154 return t2;
155 }
156 ```
157
158 The `new Class(...)` inside the loop has no memoization guards because scope @4 was pruned. The `new Class()` outside the loop retains its memoization via scope @5.