| 1 | # alignReactiveScopesToBlockScopesHIR |
| 2 | |
| 3 | ## File |
| 4 | `src/ReactiveScopes/AlignReactiveScopesToBlockScopesHIR.ts` |
| 5 | |
| 6 | ## Purpose |
| 7 | This is the **2nd of 4 passes** that determine how to break a function into discrete reactive scopes (independently memoizable units of code). The pass aligns reactive scope boundaries to control flow (block scope) boundaries. |
| 8 | |
| 9 | The problem it solves: Prior inference passes assign reactive scopes to operands based on mutation ranges at arbitrary instruction points in the control-flow graph. However, to generate memoization blocks around instructions, scopes must be aligned to block-scope boundaries -- you cannot memoize half of a loop or half of an if-block. |
| 10 | |
| 11 | **Example from the source code comments:** |
| 12 | ```javascript |
| 13 | function foo(cond, a) { |
| 14 | // original scope end |
| 15 | // expanded scope end |
| 16 | const x = []; | | |
| 17 | if (cond) { | | |
| 18 | ... | | |
| 19 | x.push(a); <--- original scope ended here |
| 20 | ... | |
| 21 | } <--- scope must extend to here |
| 22 | } |
| 23 | ``` |
| 24 | |
| 25 | ## Input Invariants |
| 26 | - `InferReactiveScopeVariables` has run: Each identifier has been assigned a `ReactiveScope` with a `range` (start/end instruction IDs) based on mutation analysis |
| 27 | - The HIR is in SSA form: Blocks have unique IDs, instructions have unique IDs, and control flow is represented with basic blocks |
| 28 | - Each block has a terminal with possible successors and fallthroughs |
| 29 | - Each scope has a mutable range `{start: InstructionId, end: InstructionId}` indicating when the scope is active |
| 30 | |
| 31 | ## Output Guarantees |
| 32 | - **Scopes end at valid block boundaries**: A reactive scope may only end at the same block scope level as it began. The scope's `range.end` is updated to the first instruction of the fallthrough block after any control flow structure that the scope overlaps |
| 33 | - **Scopes start at valid block boundaries**: For labeled breaks (gotos to a label), scopes that extend beyond the goto have their `range.start` extended back to include the label |
| 34 | - **Value blocks (ternary, logical, optional) are handled specially**: Scopes inside value blocks are extended to align with the outer block scope's instruction range |
| 35 | |
| 36 | ## Algorithm |
| 37 | |
| 38 | The pass performs a single forward traversal over all blocks: |
| 39 | |
| 40 | ### 1. Tracking Active Scopes |
| 41 | - Maintains `activeScopes: Set<ReactiveScope>` - scopes whose range overlaps the current block |
| 42 | - Maintains `activeBlockFallthroughRanges: Array<{range, fallthrough}>` - stack of pending block-fallthrough ranges |
| 43 | |
| 44 | ### 2. Per-Block Processing |
| 45 | For each block: |
| 46 | - Prune `activeScopes` to only those that extend past the current block's start |
| 47 | - If this block is a fallthrough target, pop the range from the stack and extend all active scopes' start to the range start |
| 48 | |
| 49 | ### 3. Recording Places |
| 50 | For each instruction lvalue and operand: |
| 51 | - If the place has a scope, add it to `activeScopes` |
| 52 | - If inside a value block, extend the scope's range to match the value block's outer range |
| 53 | |
| 54 | ### 4. Handling Block Fallthroughs |
| 55 | When a terminal has a fallthrough (not a simple branch): |
| 56 | - Extend all active scopes whose `range.end > terminal.id` to at least the first instruction of the fallthrough block |
| 57 | - Push the fallthrough range onto the stack for future scopes |
| 58 | |
| 59 | ### 5. Handling Labeled Breaks (Goto) |
| 60 | When encountering a goto to a label (not the natural fallthrough): |
| 61 | - Find the corresponding fallthrough range on the stack |
| 62 | - Extend all active scopes to span from the label start to its fallthrough end |
| 63 | |
| 64 | ### 6. Value Block Handling |
| 65 | For ternary, logical, and optional terminals: |
| 66 | - Create `ValueBlockNode` to track the outer block's instruction range |
| 67 | - Scopes inside value blocks inherit this range, ensuring they align to the outer block scope |
| 68 | |
| 69 | ## Key Data Structures |
| 70 | |
| 71 | ```typescript |
| 72 | type ValueBlockNode = { |
| 73 | kind: 'node'; |
| 74 | id: InstructionId; |
| 75 | valueRange: MutableRange; // Range of outer block scope |
| 76 | children: Array<ValueBlockNode | ReactiveScopeNode>; |
| 77 | }; |
| 78 | |
| 79 | type ReactiveScopeNode = { |
| 80 | kind: 'scope'; |
| 81 | id: InstructionId; |
| 82 | scope: ReactiveScope; |
| 83 | }; |
| 84 | |
| 85 | // Tracked during traversal: |
| 86 | activeBlockFallthroughRanges: Array<{ |
| 87 | range: InstructionRange; |
| 88 | fallthrough: BlockId; |
| 89 | }>; |
| 90 | activeScopes: Set<ReactiveScope>; |
| 91 | valueBlockNodes: Map<BlockId, ValueBlockNode>; |
| 92 | ``` |
| 93 | |
| 94 | ## Edge Cases |
| 95 | |
| 96 | ### Labeled Breaks |
| 97 | When a `goto` jumps to a label (not the natural fallthrough), scopes must be extended to include the entire labeled block range, preventing the break from jumping out of the scope. |
| 98 | |
| 99 | ### Value Blocks (Ternary/Logical/Optional) |
| 100 | These create nested "value" contexts. Scopes inside must be aligned to the outer block scope's boundaries, not the value block's boundaries. |
| 101 | |
| 102 | ### Nested Control Flow |
| 103 | Deeply nested if-statements require the scope to be extended through all levels back to the outermost block where the scope started. |
| 104 | |
| 105 | ### do-while and try/catch |
| 106 | The terminal's successor might be a block (not value block), which is handled specially. |
| 107 | |
| 108 | ## TODOs |
| 109 | 1. `// TODO: consider pruning activeScopes per instruction` - Currently, `activeScopes` is only pruned at block start points. Some scopes may no longer be active by the time a goto is encountered. |
| 110 | |
| 111 | 2. `// TODO: add a variant of eachTerminalSuccessor() that visits _all_ successors, not just those that are direct successors for normal control-flow ordering.` - The current implementation uses `mapTerminalSuccessors` which may not visit all successors in all cases. |
| 112 | |
| 113 | ## Example |
| 114 | |
| 115 | ### Fixture: `extend-scopes-if.js` |
| 116 | |
| 117 | **Input:** |
| 118 | ```javascript |
| 119 | function foo(a, b, c) { |
| 120 | let x = []; |
| 121 | if (a) { |
| 122 | if (b) { |
| 123 | if (c) { |
| 124 | x.push(0); // Mutation of x ends here (instruction 12-13) |
| 125 | } |
| 126 | } |
| 127 | } |
| 128 | if (x.length) { // instruction 16 |
| 129 | return x; |
| 130 | } |
| 131 | return null; |
| 132 | } |
| 133 | ``` |
| 134 | |
| 135 | **Before AlignReactiveScopesToBlockScopesHIR:** |
| 136 | ``` |
| 137 | x$23_@0[1:13] // Scope range 1-13 |
| 138 | ``` |
| 139 | The scope for `x` ends at instruction 13 (inside the innermost if block). |
| 140 | |
| 141 | **After AlignReactiveScopesToBlockScopesHIR:** |
| 142 | ``` |
| 143 | x$23_@0[1:16] // Scope range extended to 1-16 |
| 144 | ``` |
| 145 | The scope is extended to instruction 16 (the first instruction after all the nested if-blocks), aligning to the block scope boundary. |
| 146 | |
| 147 | **Generated Code:** |
| 148 | ```javascript |
| 149 | function foo(a, b, c) { |
| 150 | const $ = _c(4); |
| 151 | let x; |
| 152 | if ($[0] !== a || $[1] !== b || $[2] !== c) { |
| 153 | x = []; |
| 154 | if (a) { |
| 155 | if (b) { |
| 156 | if (c) { |
| 157 | x.push(0); |
| 158 | } |
| 159 | } |
| 160 | } |
| 161 | // Scope ends here, after ALL the if-blocks |
| 162 | $[0] = a; |
| 163 | $[1] = b; |
| 164 | $[2] = c; |
| 165 | $[3] = x; |
| 166 | } else { |
| 167 | x = $[3]; |
| 168 | } |
| 169 | // Code outside the scope |
| 170 | if (x.length) { |
| 171 | return x; |
| 172 | } |
| 173 | return null; |
| 174 | } |
| 175 | ``` |
| 176 | |
| 177 | The memoization block correctly wraps the entire nested if-structure, not just part of it. |