@samitouri / QOS-React
Code Commits Issues Pulls Sessions CI/CD
main
main
md 158 lines 6.27 KB
Rendered Raw
1 # propagateScopeDependenciesHIR
2
3 ## File
4 `src/HIR/PropagateScopeDependenciesHIR.ts`
5
6 ## Purpose
7 The `propagateScopeDependenciesHIR` pass is responsible for computing and assigning the **dependencies** for each reactive scope in the compiled function. Dependencies are the external values that a scope reads, which determine when the scope needs to re-execute. This is a critical step for memoization correctness - the compiler must track exactly which values a scope depends on so it can generate proper cache invalidation checks.
8
9 The pass also populates:
10 - `scope.dependencies` - The set of `ReactiveScopeDependency` objects the scope reads
11 - `scope.declarations` - Values declared within the scope that are used outside it
12
13 ## Input Invariants
14 - Reactive scopes must be established (pass runs after `BuildReactiveScopeTerminalsHIR`)
15 - The function must be in SSA form
16 - `InferMutationAliasingRanges` must have run to establish when values are being mutated
17 - `InferReactivePlaces` marks which identifiers are reactive
18 - Scope ranges have been aligned and normalized by earlier passes
19
20 ## Output Guarantees
21 After this pass completes:
22
23 1. Each `ReactiveScope.dependencies` contains the minimal set of dependencies that:
24 - Were declared before the scope started
25 - Are read within the scope
26 - Are not ref values (which are always mutable)
27 - Are not object methods (which get codegen'd back into object literals)
28
29 2. Each `ReactiveScope.declarations` contains identifiers that:
30 - Are assigned within the scope
31 - Are used outside the scope (need to be exposed as scope outputs)
32
33 3. Property load chains are resolved to their root identifiers with paths (e.g., `props.user.name` becomes `{identifier: props, path: ["user", "name"]}`)
34
35 4. Optional chains are handled correctly, distinguishing between `a?.b` and `a.b` access types
36
37 ## Algorithm
38
39 ### Phase 1: Build Sidemaps
40
41 1. **findTemporariesUsedOutsideDeclaringScope**: Identifies temporaries that are used outside the scope where they were declared (cannot be hoisted/reordered safely)
42
43 2. **collectTemporariesSidemap**: Creates a mapping from temporary IdentifierIds to their source `ReactiveScopeDependency`. For example:
44 ```
45 $0 = LoadLocal 'a'
46 $1 = PropertyLoad $0.'b'
47 ```
48 Maps `$1.id` to `{identifier: a, path: [{property: 'b', optional: false}]}`
49
50 3. **collectOptionalChainSidemap**: Traverses optional chain blocks to map temporaries within optional chains to their full optional dependency path
51
52 4. **collectHoistablePropertyLoads**: Uses CFG analysis to determine which property loads can be safely hoisted
53
54 ### Phase 2: Collect Dependencies
55
56 The `collectDependencies` function traverses the HIR, maintaining a stack of active scopes:
57
58 1. **Scope Entry/Exit**: When entering a scope terminal, push a new dependency array. When exiting, propagate collected dependencies to parent scopes if valid.
59
60 2. **Instruction Processing**: For each instruction:
61 - Declare the lvalue with its instruction id and current scope
62 - Visit operands to record them as potential dependencies
63 - Handle special cases like `StoreLocal` (tracks reassignments), `Destructure`, `PropertyLoad`, etc.
64
65 3. **Dependency Validation** (`#checkValidDependency`):
66 - Skip ref values (`isRefValueType`)
67 - Skip object methods (`isObjectMethodType`)
68 - Only include if declared before scope start
69
70 ### Phase 3: Derive Minimal Dependencies
71
72 For each scope, use `ReactiveScopeDependencyTreeHIR` to:
73 1. Build a tree from hoistable property loads
74 2. Add all collected dependencies to the tree
75 3. Truncate dependencies at their maximal safe-to-evaluate subpath
76 4. Derive the minimal set (removing redundant nested dependencies)
77
78 ## Key Data Structures
79
80 ### ReactiveScopeDependency
81 ```typescript
82 type ReactiveScopeDependency = {
83 identifier: Identifier; // Root identifier
84 reactive: boolean; // Whether the value is reactive
85 path: DependencyPathEntry[]; // Chain of property accesses
86 }
87 ```
88
89 ### DependencyPathEntry
90 ```typescript
91 type DependencyPathEntry = {
92 property: PropertyLiteral; // Property name
93 optional: boolean; // Is this `?.` access?
94 }
95 ```
96
97 ### DependencyCollectionContext
98 Maintains:
99 - `#declarations`: Map of DeclarationId to {id, scope} recording where each value was declared
100 - `#reassignments`: Map of Identifier to latest assignment info
101 - `#scopes`: Stack of currently active ReactiveScopes
102 - `#dependencies`: Stack of dependency arrays (one per active scope)
103 - `#temporaries`: Sidemap for resolving property loads
104
105 ### ReactiveScopeDependencyTreeHIR
106 A tree structure for efficient dependency deduplication that stores hoistable objects, tracks access types, and computes minimal dependencies.
107
108 ## Edge Cases
109
110 ### Values Used Outside Declaring Scope
111 If a temporary is used outside its declaring scope, it cannot be tracked in the sidemap because reordering the read would be invalid.
112
113 ### Ref.current Access
114 Accessing `ref.current` is treated specially - the dependency is truncated to just `ref`.
115
116 ### Optional Chains
117 Optional chains like `a?.b?.c` produce different dependency paths than `a.b.c`. The pass distinguishes them and may merge optional loads into unconditional ones when control flow proves the object is non-null.
118
119 ### Inner Functions
120 Dependencies from inner functions are collected recursively but with special handling for context variables.
121
122 ### Phi Nodes
123 When a value comes from multiple control flow paths, optional chain dependencies from phi operands are also visited.
124
125 ## TODOs
126 1. Line 374-375: `// TODO(mofeiZ): understand optional chaining` - More documentation needed for optional chain handling
127
128 ## Example
129
130 ### Fixture: `reactive-control-dependency-if.js`
131
132 **Input:**
133 ```javascript
134 function Component(props) {
135 let x;
136 if (props.cond) {
137 x = 1;
138 } else {
139 x = 2;
140 }
141 return [x];
142 }
143 ```
144
145 **Before PropagateScopeDependenciesHIR:**
146 ```
147 Scope scope @0 [12:15] dependencies=[] declarations=[] reassignments=[] block=bb9
148 ```
149
150 **After PropagateScopeDependenciesHIR:**
151 ```
152 Scope scope @0 [12:15] dependencies=[x$24:TPrimitive] declarations=[$26_@0] reassignments=[] block=bb9
153 ```
154
155 The pass identified that:
156 - The scope at `[x]` depends on `x$24` (the phi node result from the if/else branches)
157 - Even though `x` is assigned to constants (1 or 2), its value depends on the reactive control flow condition `props.cond`
158 - The scope declares `$26_@0` (the array output)