| 1 | /** |
| 2 | * Copyright (c) Meta Platforms, Inc. and affiliates. |
| 3 | * |
| 4 | * This source code is licensed under the MIT license found in the |
| 5 | * LICENSE file in the root directory of this source tree. |
| 6 | */ |
| 7 | |
| 8 | import {CompilerDiagnostic} from '../CompilerError'; |
| 9 | import { |
| 10 | FunctionExpression, |
| 11 | GeneratedSource, |
| 12 | Hole, |
| 13 | IdentifierId, |
| 14 | ObjectMethod, |
| 15 | Place, |
| 16 | SourceLocation, |
| 17 | SpreadPattern, |
| 18 | ValueKind, |
| 19 | ValueReason, |
| 20 | } from '../HIR'; |
| 21 | import {FunctionSignature} from '../HIR/ObjectShape'; |
| 22 | import {printSourceLocation} from '../HIR/PrintHIR'; |
| 23 | |
| 24 | /** |
| 25 | * `AliasingEffect` describes a set of "effects" that an instruction/terminal has on one or |
| 26 | * more values in a program. These effects include mutation of values, freezing values, |
| 27 | * tracking data flow between values, and other specialized cases. |
| 28 | */ |
| 29 | export type AliasingEffect = |
| 30 | /** |
| 31 | * Marks the given value and its direct aliases as frozen. |
| 32 | * |
| 33 | * Captured values are *not* considered frozen, because we cannot be sure that a previously |
| 34 | * captured value will still be captured at the point of the freeze. |
| 35 | * |
| 36 | * For example: |
| 37 | * const x = {}; |
| 38 | * const y = [x]; |
| 39 | * y.pop(); // y dosn't contain x anymore! |
| 40 | * freeze(y); |
| 41 | * mutate(x); // safe to mutate! |
| 42 | * |
| 43 | * The exception to this is FunctionExpressions - since it is impossible to change which |
| 44 | * value a function closes over[1] we can transitively freeze functions and their captures. |
| 45 | * |
| 46 | * [1] Except for `let` values that are reassigned and closed over by a function, but we |
| 47 | * handle this explicitly with StoreContext/LoadContext. |
| 48 | */ |
| 49 | | {kind: 'Freeze'; value: Place; reason: ValueReason} |
| 50 | /** |
| 51 | * Mutate the value and any direct aliases (not captures). Errors if the value is not mutable. |
| 52 | */ |
| 53 | | {kind: 'Mutate'; value: Place; reason?: MutationReason | null} |
| 54 | /** |
| 55 | * Mutate the value and any direct aliases (not captures), but only if the value is known mutable. |
| 56 | * This should be rare. |
| 57 | * |
| 58 | * TODO: this is only used for IteratorNext, but even then MutateTransitiveConditionally is more |
| 59 | * correct for iterators of unknown types. |
| 60 | */ |
| 61 | | {kind: 'MutateConditionally'; value: Place} |
| 62 | /** |
| 63 | * Mutate the value, any direct aliases, and any transitive captures. Errors if the value is not mutable. |
| 64 | */ |
| 65 | | {kind: 'MutateTransitive'; value: Place} |
| 66 | /** |
| 67 | * Mutates any of the value, its direct aliases, and its transitive captures that are mutable. |
| 68 | */ |
| 69 | | {kind: 'MutateTransitiveConditionally'; value: Place} |
| 70 | /** |
| 71 | * Records information flow from `from` to `into` in cases where local mutation of the destination |
| 72 | * will *not* mutate the source: |
| 73 | * |
| 74 | * - Capture a -> b and Mutate(b) X=> (does not imply) Mutate(a) |
| 75 | * - Capture a -> b and MutateTransitive(b) => (does imply) Mutate(a) |
| 76 | * |
| 77 | * Example: `array.push(item)`. Information from item is captured into array, but there is not a |
| 78 | * direct aliasing, and local mutations of array will not modify item. |
| 79 | */ |
| 80 | | {kind: 'Capture'; from: Place; into: Place} |
| 81 | /** |
| 82 | * Records information flow from `from` to `into` in cases where local mutation of the destination |
| 83 | * *will* mutate the source: |
| 84 | * |
| 85 | * - Alias a -> b and Mutate(b) => (does imply) Mutate(a) |
| 86 | * - Alias a -> b and MutateTransitive(b) => (does imply) Mutate(a) |
| 87 | * |
| 88 | * Example: `c = identity(a)`. We don't know what `identity()` returns so we can't use Assign. |
| 89 | * But we have to assume that it _could_ be returning its input, such that a local mutation of |
| 90 | * c could be mutating a. |
| 91 | */ |
| 92 | | {kind: 'Alias'; from: Place; into: Place} |
| 93 | |
| 94 | /** |
| 95 | * Indicates the potential for information flow from `from` to `into`. This is used for a specific |
| 96 | * case: functions with unknown signatures. If the compiler sees a call such as `foo(x)`, it has to |
| 97 | * consider several possibilities (which may depend on the arguments): |
| 98 | * - foo(x) returns a new mutable value that does not capture any information from x. |
| 99 | * - foo(x) returns a new mutable value that *does* capture information from x. |
| 100 | * - foo(x) returns x itself, ie foo is the identity function |
| 101 | * |
| 102 | * The same is true of functions that take multiple arguments: `cond(a, b, c)` could conditionally |
| 103 | * return b or c depending on the value of a. |
| 104 | * |
| 105 | * To represent this case, MaybeAlias represents the fact that an aliasing relationship could exist. |
| 106 | * Any mutations that flow through this relationship automatically become conditional. |
| 107 | */ |
| 108 | | {kind: 'MaybeAlias'; from: Place; into: Place} |
| 109 | |
| 110 | /** |
| 111 | * Records direct assignment: `into = from`. |
| 112 | */ |
| 113 | | {kind: 'Assign'; from: Place; into: Place} |
| 114 | /** |
| 115 | * Creates a value of the given type at the given place |
| 116 | */ |
| 117 | | {kind: 'Create'; into: Place; value: ValueKind; reason: ValueReason} |
| 118 | /** |
| 119 | * Creates a new value with the same kind as the starting value. |
| 120 | */ |
| 121 | | {kind: 'CreateFrom'; from: Place; into: Place} |
| 122 | /** |
| 123 | * Immutable data flow, used for escape analysis. Does not influence mutable range analysis: |
| 124 | */ |
| 125 | | {kind: 'ImmutableCapture'; from: Place; into: Place} |
| 126 | /** |
| 127 | * Calls the function at the given place with the given arguments either captured or aliased, |
| 128 | * and captures/aliases the result into the given place. |
| 129 | */ |
| 130 | | { |
| 131 | kind: 'Apply'; |
| 132 | receiver: Place; |
| 133 | function: Place; |
| 134 | mutatesFunction: boolean; |
| 135 | args: Array<Place | SpreadPattern | Hole>; |
| 136 | into: Place; |
| 137 | signature: FunctionSignature | null; |
| 138 | loc: SourceLocation; |
| 139 | } |
| 140 | /** |
| 141 | * Constructs a function value with the given captures. The mutability of the function |
| 142 | * will be determined by the mutability of the capture values when evaluated. |
| 143 | */ |
| 144 | | { |
| 145 | kind: 'CreateFunction'; |
| 146 | captures: Array<Place>; |
| 147 | function: FunctionExpression | ObjectMethod; |
| 148 | into: Place; |
| 149 | } |
| 150 | /** |
| 151 | * Mutation of a value known to be immutable |
| 152 | */ |
| 153 | | {kind: 'MutateFrozen'; place: Place; error: CompilerDiagnostic} |
| 154 | /** |
| 155 | * Mutation of a global |
| 156 | */ |
| 157 | | { |
| 158 | kind: 'MutateGlobal'; |
| 159 | place: Place; |
| 160 | error: CompilerDiagnostic; |
| 161 | } |
| 162 | /** |
| 163 | * Indicates a side-effect that is not safe during render |
| 164 | */ |
| 165 | | {kind: 'Impure'; place: Place; error: CompilerDiagnostic} |
| 166 | /** |
| 167 | * Indicates that a given place is accessed during render. Used to distingush |
| 168 | * hook arguments that are known to be called immediately vs those used for |
| 169 | * event handlers/effects, and for JSX values known to be called during render |
| 170 | * (tags, children) vs those that may be events/effect (other props). |
| 171 | */ |
| 172 | | { |
| 173 | kind: 'Render'; |
| 174 | place: Place; |
| 175 | }; |
| 176 | |
| 177 | export type MutationReason = {kind: 'AssignCurrentProperty'}; |
| 178 | |
| 179 | export function hashEffect(effect: AliasingEffect): string { |
| 180 | switch (effect.kind) { |
| 181 | case 'Apply': { |
| 182 | return [ |
| 183 | effect.kind, |
| 184 | effect.receiver.identifier.id, |
| 185 | effect.function.identifier.id, |
| 186 | effect.mutatesFunction, |
| 187 | effect.args |
| 188 | .map(a => { |
| 189 | if (a.kind === 'Hole') { |
| 190 | return ''; |
| 191 | } else if (a.kind === 'Identifier') { |
| 192 | return a.identifier.id; |
| 193 | } else { |
| 194 | return `...${a.place.identifier.id}`; |
| 195 | } |
| 196 | }) |
| 197 | .join(','), |
| 198 | effect.into.identifier.id, |
| 199 | ].join(':'); |
| 200 | } |
| 201 | case 'CreateFrom': |
| 202 | case 'ImmutableCapture': |
| 203 | case 'Assign': |
| 204 | case 'Alias': |
| 205 | case 'Capture': |
| 206 | case 'MaybeAlias': { |
| 207 | return [ |
| 208 | effect.kind, |
| 209 | effect.from.identifier.id, |
| 210 | effect.into.identifier.id, |
| 211 | ].join(':'); |
| 212 | } |
| 213 | case 'Create': { |
| 214 | return [ |
| 215 | effect.kind, |
| 216 | effect.into.identifier.id, |
| 217 | effect.value, |
| 218 | effect.reason, |
| 219 | ].join(':'); |
| 220 | } |
| 221 | case 'Freeze': { |
| 222 | return [effect.kind, effect.value.identifier.id, effect.reason].join(':'); |
| 223 | } |
| 224 | case 'Impure': |
| 225 | case 'Render': { |
| 226 | return [effect.kind, effect.place.identifier.id].join(':'); |
| 227 | } |
| 228 | case 'MutateFrozen': |
| 229 | case 'MutateGlobal': { |
| 230 | return [ |
| 231 | effect.kind, |
| 232 | effect.place.identifier.id, |
| 233 | effect.error.severity, |
| 234 | effect.error.reason, |
| 235 | effect.error.description, |
| 236 | printSourceLocation(effect.error.primaryLocation() ?? GeneratedSource), |
| 237 | ].join(':'); |
| 238 | } |
| 239 | case 'Mutate': |
| 240 | case 'MutateConditionally': |
| 241 | case 'MutateTransitive': |
| 242 | case 'MutateTransitiveConditionally': { |
| 243 | return [effect.kind, effect.value.identifier.id].join(':'); |
| 244 | } |
| 245 | case 'CreateFunction': { |
| 246 | return [ |
| 247 | effect.kind, |
| 248 | effect.into.identifier.id, |
| 249 | // return places are a unique way to identify functions themselves |
| 250 | effect.function.loweredFunc.func.returns.identifier.id, |
| 251 | effect.captures.map(p => p.identifier.id).join(','), |
| 252 | ].join(':'); |
| 253 | } |
| 254 | } |
| 255 | } |
| 256 | |
| 257 | export type AliasingSignature = { |
| 258 | receiver: IdentifierId; |
| 259 | params: Array<IdentifierId>; |
| 260 | rest: IdentifierId | null; |
| 261 | returns: IdentifierId; |
| 262 | effects: Array<AliasingEffect>; |
| 263 | temporaries: Array<Place>; |
| 264 | }; |