@samitouri / QOS-React
Code Commits Issues Pulls Sessions CI/CD
main
main
md 169 lines 6.93 KB
Rendered Raw
1 # inferReactivePlaces
2
3 ## File
4 `src/Inference/InferReactivePlaces.ts`
5
6 ## Purpose
7 Determines which `Place`s (identifiers and temporaries) in the HIR are **reactive** - meaning they may *semantically* change over the course of the component or hook's lifetime. This information is critical for memoization: reactive places form the dependencies that, when changed, should invalidate cached values.
8
9 A place is reactive if it derives from any source of reactivity:
10 1. **Props** - Component parameters may change between renders
11 2. **Hooks** - Hooks can access state or context which can change
12 3. **`use` operator** - Can access context which may change
13 4. **Mutation with reactive operands** - Values mutated in instructions that have reactive operands become reactive themselves
14 5. **Conditional assignment based on reactive control flow** - Values assigned in branches controlled by reactive conditions become reactive
15
16 ## Input Invariants
17 - HIR is in SSA form with phi nodes at join points
18 - `inferMutationAliasingEffects` and `inferMutationAliasingRanges` have run, establishing:
19 - Effect annotations on operands (Effect.Capture, Effect.Store, Effect.Mutate, etc.)
20 - Mutable ranges on identifiers
21 - Aliasing relationships captured by `findDisjointMutableValues`
22 - All operands have known effects (asserts on `Effect.Unknown`)
23
24 ## Output Guarantees
25 - Every reactive Place has `place.reactive = true`
26 - Reactivity is transitively complete (derived from reactive → reactive)
27 - All identifiers in a mutable alias group share reactivity
28 - Reactivity is propagated to operands used within nested function expressions
29
30 ## Algorithm
31 The algorithm uses **fixpoint iteration** to propagate reactivity forward through the control-flow graph:
32
33 ### Initialization
34 1. Create a `ReactivityMap` backed by disjoint sets of mutably-aliased identifiers
35 2. Mark all function parameters as reactive (props are reactive by definition)
36 3. Create a `ControlDominators` helper to identify blocks controlled by reactive conditions
37
38 ### Fixpoint Loop
39 Iterate until no changes occur:
40
41 For each block:
42 1. **Phi Nodes**: Mark phi nodes reactive if:
43 - Any operand is reactive, OR
44 - Any predecessor block is controlled by a reactive condition (control-flow dependency)
45
46 2. **Instructions**: For each instruction:
47 - Track stable identifier sources (for hooks like `useRef`, `useState` dispatch)
48 - Check if any operand is reactive
49 - Hook calls and `use` operator are sources of reactivity
50 - If instruction has reactive input:
51 - Mark lvalues reactive (unless they are known-stable like `setState` functions)
52 - If instruction has reactive input OR is in reactive-controlled block:
53 - Mark mutable operands (Capture, Store, Mutate effects) as reactive
54
55 3. **Terminals**: Check terminal operands for reactivity
56
57 ### Post-processing
58 Propagate reactivity to inner functions (nested `FunctionExpression` and `ObjectMethod`).
59
60 ## Key Data Structures
61
62 ### ReactivityMap
63 ```typescript
64 class ReactivityMap {
65 hasChanges: boolean = false; // Tracks if fixpoint changed
66 reactive: Set<IdentifierId> = new Set(); // Set of reactive identifiers
67 aliasedIdentifiers: DisjointSet<Identifier>; // Mutable alias groups
68 }
69 ```
70 - Uses disjoint sets so that when one identifier in an alias group becomes reactive, they all are effectively reactive
71 - `isReactive(place)` checks and marks `place.reactive = true` as a side effect
72 - `snapshot()` resets change tracking and returns whether changes occurred
73
74 ### StableSidemap
75 ```typescript
76 class StableSidemap {
77 map: Map<IdentifierId, {isStable: boolean}> = new Map();
78 }
79 ```
80 Tracks sources of stability (e.g., `useState()[1]` dispatch function). Forward data-flow analysis that:
81 - Records hook calls that return stable types
82 - Propagates stability through PropertyLoad and Destructure from stable containers
83 - Propagates through LoadLocal and StoreLocal
84
85 ### ControlDominators
86 Uses post-dominator frontier analysis to determine which blocks are controlled by reactive branch conditions.
87
88 ## Edge Cases
89
90 ### Backward Reactivity Propagation via Mutable Aliasing
91 ```javascript
92 const x = [];
93 const z = [x];
94 x.push(props.input);
95 return <div>{z}</div>;
96 ```
97 Here `z` aliases `x` which is later mutated with reactive data. The disjoint set ensures `z` becomes reactive even though the mutation happens after its creation.
98
99 ### Stable Types Are Not Reactive
100 ```javascript
101 const [state, setState] = useState();
102 // setState is stable - not marked reactive despite coming from reactive hook
103 ```
104 The `StableSidemap` tracks these and skips marking them reactive.
105
106 ### Ternary with Stable Values Still Reactive
107 ```javascript
108 props.cond ? setState1 : setState2
109 ```
110 Even though both branches are stable types, the result depends on reactive control flow, so it cannot be marked non-reactive just based on type.
111
112 ### Phi Nodes with Reactive Predecessors
113 When a phi's predecessor block is controlled by a reactive condition, the phi becomes reactive even if its operands are all non-reactive constants.
114
115 ## TODOs
116 No explicit TODO comments are present in the source file. However, comments note:
117
118 - **ComputedLoads not handled for stability**: Only PropertyLoad propagates stability from containers, not ComputedLoad. The comment notes this is safe because stable containers have differently-typed elements, but ComputedLoad handling could be added.
119
120 ## Example
121
122 ### Fixture: `reactive-dependency-fixpoint.js`
123
124 **Input:**
125 ```javascript
126 function Component(props) {
127 let x = 0;
128 let y = 0;
129 while (x === 0) {
130 x = y;
131 y = props.value;
132 }
133 return [x];
134 }
135 ```
136
137 **Before InferReactivePlaces:**
138 ```
139 bb1 (loop):
140 store x$26:TPhi:TPhi: phi(bb0: read x$21:TPrimitive, bb3: read x$32:TPhi)
141 store y$30:TPhi:TPhi: phi(bb0: read y$24:TPrimitive, bb3: read y$37)
142 ...
143 bb3 (block):
144 [12] mutate? $35 = LoadLocal read props$19
145 [13] mutate? $36 = PropertyLoad read $35.value
146 [14] mutate? $38 = StoreLocal Reassign mutate? y$37 = read $36
147 ```
148
149 **After InferReactivePlaces:**
150 ```
151 bb1 (loop):
152 store x$26:TPhi{reactive}:TPhi: phi(bb0: read x$21:TPrimitive, bb3: read x$32:TPhi{reactive})
153 store y$30:TPhi{reactive}:TPhi: phi(bb0: read y$24:TPrimitive, bb3: read y$37{reactive})
154 [6] mutate? $27:TPhi{reactive} = LoadLocal read x$26:TPhi{reactive}
155 ...
156 bb3 (block):
157 [12] mutate? $35{reactive} = LoadLocal read props$19{reactive}
158 [13] mutate? $36{reactive} = PropertyLoad read $35{reactive}.value
159 [14] mutate? $38{reactive} = StoreLocal Reassign mutate? y$37{reactive} = read $36{reactive}
160 ```
161
162 **Key observations:**
163 - `props$19` is marked `{reactive}` as a function parameter
164 - The reactivity propagates through the loop:
165 - First iteration: `y$37` becomes reactive from `props.value`
166 - Second iteration: `x$32` becomes reactive from `y$30` (which is reactive via the phi from `y$37`)
167 - The phi nodes `x$26` and `y$30` become reactive because their bb3 operands are reactive
168 - The fixpoint algorithm handles this backward propagation through the loop correctly
169 - The final output `$40` is reactive, so the array `[x]` will be memoized with `x` as a dependency