| 1 | # inferMutationAliasingEffects |
| 2 | |
| 3 | ## File |
| 4 | `src/Inference/InferMutationAliasingEffects.ts` |
| 5 | |
| 6 | ## Purpose |
| 7 | Infers the mutation and aliasing effects for all instructions and terminals in the HIR, making the effects of built-in instructions/functions as well as user-defined functions explicit. These effects form the basis for subsequent analysis to determine the mutable range of each value in the program and for validation against invalid code patterns like mutating frozen values. |
| 8 | |
| 9 | ## Input Invariants |
| 10 | - HIR must be in SSA form (run after SSA pass) |
| 11 | - Types must be inferred (run after InferTypes pass) |
| 12 | - Functions must be analyzed (run after AnalyseFunctions pass) - this provides `aliasingEffects` on FunctionExpressions |
| 13 | - Each instruction must have an lvalue (destination place) |
| 14 | |
| 15 | ## Output Guarantees |
| 16 | - Every instruction has an `effects` array (or null if no effects) containing `AliasingEffect` objects |
| 17 | - Terminals that affect data flow (return, try/catch) have their `effects` populated |
| 18 | - Each instruction's lvalue is guaranteed to be defined in the inference state after visiting |
| 19 | - Effects describe: creation of values, data flow (Assign, Alias, Capture), mutations (Mutate, MutateTransitive), freezing, and errors (MutateFrozen, MutateGlobal, Impure) |
| 20 | |
| 21 | ## Algorithm |
| 22 | The pass uses abstract interpretation with the following key phases: |
| 23 | |
| 24 | 1. **Initialization**: |
| 25 | - Create initial `InferenceState` mapping identifiers to abstract values |
| 26 | - Initialize context variables as `ValueKind.Context` |
| 27 | - Initialize parameters as `ValueKind.Frozen` (for top-level components/hooks) or `ValueKind.Mutable` (for function expressions) |
| 28 | |
| 29 | 2. **Two-Phase Effect Processing**: |
| 30 | - **Phase 1 - Signature Computation**: For each instruction, compute a "candidate signature" based purely on instruction semantics and types (cached per instruction via `computeSignatureForInstruction`) |
| 31 | - **Phase 2 - Effect Application**: Apply the signature to the current abstract state via `applySignature`, which refines effects based on the actual runtime kinds of values |
| 32 | |
| 33 | 3. **Fixed-Point Iteration**: |
| 34 | - Process blocks in a worklist, queuing successors after each block |
| 35 | - Merge states at control flow join points using lattice operations |
| 36 | - Iterate until no changes occur (max 100 iterations as safety limit) |
| 37 | - Phi nodes are handled by unioning the abstract values from all predecessors |
| 38 | |
| 39 | 4. **Effect Refinement** (in `applyEffect`): |
| 40 | - `MutateConditionally` effects are dropped if value is not mutable |
| 41 | - `Capture` effects are downgraded to `ImmutableCapture` if source is frozen |
| 42 | - `Mutate` on frozen values becomes `MutateFrozen` error |
| 43 | - `Assign` from primitives/globals creates new values rather than aliasing |
| 44 | |
| 45 | ## Key Data Structures |
| 46 | |
| 47 | ### InferenceState |
| 48 | Maintains two maps: |
| 49 | - `#values: Map<InstructionValue, AbstractValue>` - Maps allocation sites to their abstract kind |
| 50 | - `#variables: Map<IdentifierId, Set<InstructionValue>>` - Maps identifiers to the set of values they may point to (set to handle phi joins) |
| 51 | |
| 52 | ### AbstractValue |
| 53 | ```typescript |
| 54 | type AbstractValue = { |
| 55 | kind: ValueKind; |
| 56 | reason: ReadonlySet<ValueReason>; |
| 57 | }; |
| 58 | ``` |
| 59 | |
| 60 | ### ValueKind (lattice) |
| 61 | ``` |
| 62 | MaybeFrozen <- top (unknown if frozen or mutable) |
| 63 | | |
| 64 | Frozen <- immutable, cannot be mutated |
| 65 | Mutable <- can be mutated locally |
| 66 | Context <- mutable box (context variables) |
| 67 | | |
| 68 | Global <- global value |
| 69 | Primitive <- copy-on-write semantics |
| 70 | ``` |
| 71 | |
| 72 | The `mergeValueKinds` function implements the lattice join: |
| 73 | - `Frozen | Mutable -> MaybeFrozen` |
| 74 | - `Context | Mutable -> Context` |
| 75 | - `Context | Frozen -> MaybeFrozen` |
| 76 | |
| 77 | ### AliasingEffect Types |
| 78 | Key effect kinds handled: |
| 79 | - **Create**: Creates a new value at a place |
| 80 | - **Assign**: Direct assignment (pointer copy) |
| 81 | - **Alias**: Mutation of destination implies mutation of source |
| 82 | - **Capture**: Information flow (MutateTransitive propagates through) |
| 83 | - **MaybeAlias**: Possible aliasing for unknown function returns |
| 84 | - **Mutate/MutateTransitive**: Direct/transitive mutation |
| 85 | - **MutateConditionally/MutateTransitiveConditionally**: Conditional versions |
| 86 | - **Freeze**: Marks value as immutable |
| 87 | - **Apply**: Function call with complex data flow |
| 88 | |
| 89 | ## Edge Cases |
| 90 | |
| 91 | 1. **Spread Destructuring from Props**: The `findNonMutatedDestructureSpreads` pre-pass identifies spread patterns from frozen values that are never mutated, allowing them to be treated as frozen. |
| 92 | |
| 93 | 2. **Hoisted Context Declarations**: Special handling for variables declared with hoisting (`HoistedConst`, `HoistedFunction`, `HoistedLet`) to detect access before declaration. |
| 94 | |
| 95 | 3. **Try-Catch Aliasing**: When a `maybe-throw` terminal is reached, call return values are aliased into the catch binding since exceptions can throw return values. |
| 96 | |
| 97 | 4. **Function Expressions**: Functions are considered mutable only if they have mutable captures or tracked side effects (MutateFrozen, MutateGlobal, Impure). |
| 98 | |
| 99 | 5. **Iterator Mutation**: Non-builtin iterators may alias their collection and mutation of the iterator is conditional. |
| 100 | |
| 101 | 6. **Array.push and Similar**: Uses legacy signature system with `Store` effect on receiver and `Capture` of arguments. |
| 102 | |
| 103 | ## TODOs |
| 104 | - `// TODO: using InstructionValue as a bit of a hack, but it's pragmatic` - context variable initialization |
| 105 | - `// TODO: call applyEffect() instead` - try-catch aliasing |
| 106 | - `// TODO: make sure we're also validating against global mutations somewhere` - global mutation validation for effects/event handlers |
| 107 | - `// TODO; include "render" here?` - whether to track Render effects in function hasTrackedSideEffects |
| 108 | - `// TODO: consider using persistent data structures to make clone cheaper` - performance optimization for state cloning |
| 109 | - `// TODO check this` and `// TODO: what kind here???` - DeclareLocal value kinds |
| 110 | |
| 111 | ## Example |
| 112 | |
| 113 | For the code: |
| 114 | ```javascript |
| 115 | const arr = []; |
| 116 | arr.push({}); |
| 117 | arr.push(x, y); |
| 118 | ``` |
| 119 | |
| 120 | After `InferMutationAliasingEffects`, the effects are: |
| 121 | |
| 122 | ``` |
| 123 | [10] $39 = Array [] |
| 124 | Create $39 = mutable // Array literal creates mutable value |
| 125 | |
| 126 | [11] $41 = StoreLocal arr$40 = $39 |
| 127 | Assign arr$40 = $39 // arr points to the array value |
| 128 | Assign $41 = $39 |
| 129 | |
| 130 | [15] $45 = MethodCall $42.push($44) |
| 131 | Apply $45 = $42.$43($44) // Records the call |
| 132 | Mutate $42 // push mutates the array |
| 133 | Capture $42 <- $44 // {} is captured into array |
| 134 | Create $45 = primitive // push returns number (length) |
| 135 | |
| 136 | [20] $50 = MethodCall $46.push($48, $49) |
| 137 | Apply $50 = $46.$47($48, $49) |
| 138 | Mutate $46 // push mutates the array |
| 139 | Capture $46 <- $48 // x captured into array |
| 140 | Capture $46 <- $49 // y captured into array |
| 141 | Create $50 = primitive |
| 142 | ``` |
| 143 | |
| 144 | The key insight is that `Mutate` effects extend the mutable range of the array, and `Capture` effects record data flow so that if the array is later frozen (e.g., returned from a component), the captured values are also considered frozen for validation purposes. |