| 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 {CompilerError, SourceLocation} from '..'; |
| 9 | import {assertNonNull} from './CollectHoistablePropertyLoads'; |
| 10 | import { |
| 11 | BlockId, |
| 12 | BasicBlock, |
| 13 | IdentifierId, |
| 14 | ReactiveScopeDependency, |
| 15 | BranchTerminal, |
| 16 | TInstruction, |
| 17 | PropertyLoad, |
| 18 | StoreLocal, |
| 19 | GotoVariant, |
| 20 | TBasicBlock, |
| 21 | OptionalTerminal, |
| 22 | HIRFunction, |
| 23 | DependencyPathEntry, |
| 24 | Instruction, |
| 25 | Terminal, |
| 26 | PropertyLiteral, |
| 27 | } from './HIR'; |
| 28 | import {printIdentifier} from './PrintHIR'; |
| 29 | |
| 30 | export function collectOptionalChainSidemap( |
| 31 | fn: HIRFunction, |
| 32 | ): OptionalChainSidemap { |
| 33 | const context: OptionalTraversalContext = { |
| 34 | currFn: fn, |
| 35 | blocks: fn.body.blocks, |
| 36 | seenOptionals: new Set(), |
| 37 | processedInstrsInOptional: new Set(), |
| 38 | temporariesReadInOptional: new Map(), |
| 39 | hoistableObjects: new Map(), |
| 40 | }; |
| 41 | traverseFunction(fn, context); |
| 42 | return { |
| 43 | temporariesReadInOptional: context.temporariesReadInOptional, |
| 44 | processedInstrsInOptional: context.processedInstrsInOptional, |
| 45 | hoistableObjects: context.hoistableObjects, |
| 46 | }; |
| 47 | } |
| 48 | export type OptionalChainSidemap = { |
| 49 | /** |
| 50 | * Stores the correct property mapping (e.g. `a?.b` instead of `a.b`) for |
| 51 | * dependency calculation. Note that we currently do not store anything on |
| 52 | * outer phi nodes. |
| 53 | */ |
| 54 | temporariesReadInOptional: ReadonlyMap<IdentifierId, ReactiveScopeDependency>; |
| 55 | /** |
| 56 | * Records instructions (PropertyLoads, StoreLocals, and test terminals) |
| 57 | * processed in this pass. When extracting dependencies in |
| 58 | * PropagateScopeDependencies, these instructions are skipped. |
| 59 | * |
| 60 | * E.g. given a?.b |
| 61 | * ``` |
| 62 | * bb0 |
| 63 | * $0 = LoadLocal 'a' |
| 64 | * test $0 then=bb1 <- Avoid adding dependencies from these instructions, as |
| 65 | * bb1 the sidemap produced by readOptionalBlock already maps |
| 66 | * $1 = PropertyLoad $0.'b' <- $1 and $2 back to a?.b. Instead, we want to add a?.b |
| 67 | * StoreLocal $2 = $1 <- as a dependency when $1 or $2 are later used in either |
| 68 | * - an unhoistable expression within an outer optional |
| 69 | * block e.g. MethodCall |
| 70 | * - a phi node (if the entire optional value is hoistable) |
| 71 | * ``` |
| 72 | * |
| 73 | * Note that mapping blockIds to their evaluated dependency path does not |
| 74 | * work, since values produced by inner optional chains may be referenced in |
| 75 | * outer ones |
| 76 | * ``` |
| 77 | * a?.b.c() |
| 78 | * -> |
| 79 | * bb0 |
| 80 | * $0 = LoadLocal 'a' |
| 81 | * test $0 then=bb1 |
| 82 | * bb1 |
| 83 | * $1 = PropertyLoad $0.'b' |
| 84 | * StoreLocal $2 = $1 |
| 85 | * goto bb2 |
| 86 | * bb2 |
| 87 | * test $2 then=bb3 |
| 88 | * bb3: |
| 89 | * $3 = PropertyLoad $2.'c' |
| 90 | * StoreLocal $4 = $3 |
| 91 | * goto bb4 |
| 92 | * bb4 |
| 93 | * test $4 then=bb5 |
| 94 | * bb5: |
| 95 | * $5 = MethodCall $2.$4() <--- here, we want to take a dep on $2 and $4! |
| 96 | * ``` |
| 97 | * |
| 98 | * Also note that InstructionIds are not unique across inner functions. |
| 99 | */ |
| 100 | processedInstrsInOptional: ReadonlySet<Instruction | Terminal>; |
| 101 | /** |
| 102 | * Records optional chains for which we can safely evaluate non-optional |
| 103 | * PropertyLoads. e.g. given `a?.b.c`, we can evaluate any load from `a?.b` at |
| 104 | * the optional terminal in bb1. |
| 105 | * ```js |
| 106 | * bb1: |
| 107 | * ... |
| 108 | * Optional optional=false test=bb2 fallth=... |
| 109 | * bb2: |
| 110 | * Optional optional=true test=bb3 fallth=... |
| 111 | * ... |
| 112 | * ``` |
| 113 | */ |
| 114 | hoistableObjects: ReadonlyMap<BlockId, ReactiveScopeDependency>; |
| 115 | }; |
| 116 | |
| 117 | type OptionalTraversalContext = { |
| 118 | currFn: HIRFunction; |
| 119 | blocks: ReadonlyMap<BlockId, BasicBlock>; |
| 120 | |
| 121 | // Track optional blocks to avoid outer calls into nested optionals |
| 122 | seenOptionals: Set<BlockId>; |
| 123 | |
| 124 | processedInstrsInOptional: Set<Instruction | Terminal>; |
| 125 | temporariesReadInOptional: Map<IdentifierId, ReactiveScopeDependency>; |
| 126 | hoistableObjects: Map<BlockId, ReactiveScopeDependency>; |
| 127 | }; |
| 128 | |
| 129 | function traverseFunction( |
| 130 | fn: HIRFunction, |
| 131 | context: OptionalTraversalContext, |
| 132 | ): void { |
| 133 | for (const [_, block] of fn.body.blocks) { |
| 134 | for (const instr of block.instructions) { |
| 135 | if ( |
| 136 | instr.value.kind === 'FunctionExpression' || |
| 137 | instr.value.kind === 'ObjectMethod' |
| 138 | ) { |
| 139 | traverseFunction(instr.value.loweredFunc.func, { |
| 140 | ...context, |
| 141 | currFn: instr.value.loweredFunc.func, |
| 142 | blocks: instr.value.loweredFunc.func.body.blocks, |
| 143 | }); |
| 144 | } |
| 145 | } |
| 146 | if ( |
| 147 | block.terminal.kind === 'optional' && |
| 148 | !context.seenOptionals.has(block.id) |
| 149 | ) { |
| 150 | traverseOptionalBlock( |
| 151 | block as TBasicBlock<OptionalTerminal>, |
| 152 | context, |
| 153 | null, |
| 154 | ); |
| 155 | } |
| 156 | } |
| 157 | } |
| 158 | /** |
| 159 | * Match the consequent and alternate blocks of an optional. |
| 160 | * @returns propertyload computed by the consequent block, or null if the |
| 161 | * consequent block is not a simple PropertyLoad. |
| 162 | */ |
| 163 | function matchOptionalTestBlock( |
| 164 | terminal: BranchTerminal, |
| 165 | blocks: ReadonlyMap<BlockId, BasicBlock>, |
| 166 | ): { |
| 167 | consequentId: IdentifierId; |
| 168 | property: PropertyLiteral; |
| 169 | propertyId: IdentifierId; |
| 170 | storeLocalInstr: Instruction; |
| 171 | consequentGoto: BlockId; |
| 172 | propertyLoadLoc: SourceLocation; |
| 173 | } | null { |
| 174 | const consequentBlock = assertNonNull(blocks.get(terminal.consequent)); |
| 175 | if ( |
| 176 | consequentBlock.instructions.length === 2 && |
| 177 | consequentBlock.instructions[0].value.kind === 'PropertyLoad' && |
| 178 | consequentBlock.instructions[1].value.kind === 'StoreLocal' |
| 179 | ) { |
| 180 | const propertyLoad: TInstruction<PropertyLoad> = consequentBlock |
| 181 | .instructions[0] as TInstruction<PropertyLoad>; |
| 182 | const storeLocal: StoreLocal = consequentBlock.instructions[1].value; |
| 183 | const storeLocalInstr = consequentBlock.instructions[1]; |
| 184 | CompilerError.invariant( |
| 185 | propertyLoad.value.object.identifier.id === terminal.test.identifier.id, |
| 186 | { |
| 187 | reason: |
| 188 | '[OptionalChainDeps] Inconsistent optional chaining property load', |
| 189 | description: `Test=${printIdentifier(terminal.test.identifier)} PropertyLoad base=${printIdentifier(propertyLoad.value.object.identifier)}`, |
| 190 | loc: propertyLoad.loc, |
| 191 | }, |
| 192 | ); |
| 193 | |
| 194 | CompilerError.invariant( |
| 195 | storeLocal.value.identifier.id === propertyLoad.lvalue.identifier.id, |
| 196 | { |
| 197 | reason: '[OptionalChainDeps] Unexpected storeLocal', |
| 198 | loc: propertyLoad.loc, |
| 199 | }, |
| 200 | ); |
| 201 | if ( |
| 202 | consequentBlock.terminal.kind !== 'goto' || |
| 203 | consequentBlock.terminal.variant !== GotoVariant.Break |
| 204 | ) { |
| 205 | return null; |
| 206 | } |
| 207 | const alternate = assertNonNull(blocks.get(terminal.alternate)); |
| 208 | |
| 209 | CompilerError.invariant( |
| 210 | alternate.instructions.length === 2 && |
| 211 | alternate.instructions[0].value.kind === 'Primitive' && |
| 212 | alternate.instructions[1].value.kind === 'StoreLocal', |
| 213 | { |
| 214 | reason: 'Unexpected alternate structure', |
| 215 | loc: terminal.loc, |
| 216 | }, |
| 217 | ); |
| 218 | |
| 219 | return { |
| 220 | consequentId: storeLocal.lvalue.place.identifier.id, |
| 221 | property: propertyLoad.value.property, |
| 222 | propertyId: propertyLoad.lvalue.identifier.id, |
| 223 | storeLocalInstr, |
| 224 | consequentGoto: consequentBlock.terminal.block, |
| 225 | propertyLoadLoc: propertyLoad.loc, |
| 226 | }; |
| 227 | } |
| 228 | return null; |
| 229 | } |
| 230 | |
| 231 | /** |
| 232 | * Traverse into the optional block and all transitively referenced blocks to |
| 233 | * collect sidemaps of optional chain dependencies. |
| 234 | * |
| 235 | * @returns the IdentifierId representing the optional block if the block and |
| 236 | * all transitively referenced optional blocks precisely represent a chain of |
| 237 | * property loads. If any part of the optional chain is not hoistable, returns |
| 238 | * null. |
| 239 | */ |
| 240 | function traverseOptionalBlock( |
| 241 | optional: TBasicBlock<OptionalTerminal>, |
| 242 | context: OptionalTraversalContext, |
| 243 | outerAlternate: BlockId | null, |
| 244 | ): IdentifierId | null { |
| 245 | context.seenOptionals.add(optional.id); |
| 246 | const maybeTest = context.blocks.get(optional.terminal.test)!; |
| 247 | let test: BranchTerminal; |
| 248 | let baseObject: ReactiveScopeDependency; |
| 249 | if (maybeTest.terminal.kind === 'branch') { |
| 250 | CompilerError.invariant(optional.terminal.optional, { |
| 251 | reason: '[OptionalChainDeps] Expect base case to be always optional', |
| 252 | loc: optional.terminal.loc, |
| 253 | }); |
| 254 | /** |
| 255 | * Optional base expressions are currently within value blocks which cannot |
| 256 | * be interrupted by scope boundaries. As such, the only dependencies we can |
| 257 | * hoist out of optional chains are property load chains with no intervening |
| 258 | * instructions. |
| 259 | * |
| 260 | * Ideally, we would be able to flatten base instructions out of optional |
| 261 | * blocks, but this would require changes to HIR. |
| 262 | * |
| 263 | * For now, only match base expressions that are straightforward |
| 264 | * PropertyLoad chains |
| 265 | */ |
| 266 | if ( |
| 267 | maybeTest.instructions.length === 0 || |
| 268 | maybeTest.instructions[0].value.kind !== 'LoadLocal' |
| 269 | ) { |
| 270 | return null; |
| 271 | } |
| 272 | const path: Array<DependencyPathEntry> = []; |
| 273 | for (let i = 1; i < maybeTest.instructions.length; i++) { |
| 274 | const instrVal = maybeTest.instructions[i].value; |
| 275 | const prevInstr = maybeTest.instructions[i - 1]; |
| 276 | if ( |
| 277 | instrVal.kind === 'PropertyLoad' && |
| 278 | instrVal.object.identifier.id === prevInstr.lvalue.identifier.id |
| 279 | ) { |
| 280 | path.push({ |
| 281 | property: instrVal.property, |
| 282 | optional: false, |
| 283 | loc: instrVal.loc, |
| 284 | }); |
| 285 | } else { |
| 286 | return null; |
| 287 | } |
| 288 | } |
| 289 | CompilerError.invariant( |
| 290 | maybeTest.terminal.test.identifier.id === |
| 291 | maybeTest.instructions.at(-1)!.lvalue.identifier.id, |
| 292 | { |
| 293 | reason: '[OptionalChainDeps] Unexpected test expression', |
| 294 | loc: maybeTest.terminal.loc, |
| 295 | }, |
| 296 | ); |
| 297 | baseObject = { |
| 298 | identifier: maybeTest.instructions[0].value.place.identifier, |
| 299 | reactive: maybeTest.instructions[0].value.place.reactive, |
| 300 | path, |
| 301 | loc: maybeTest.instructions[0].value.place.loc, |
| 302 | }; |
| 303 | test = maybeTest.terminal; |
| 304 | } else if (maybeTest.terminal.kind === 'optional') { |
| 305 | /** |
| 306 | * This is either |
| 307 | * - <inner_optional>?.property (optional=true) |
| 308 | * - <inner_optional>.property (optional=false) |
| 309 | * - <inner_optional> <other operation> |
| 310 | * - a optional base block with a separate nested optional-chain (e.g. a(c?.d)?.d) |
| 311 | */ |
| 312 | const testBlock = context.blocks.get(maybeTest.terminal.fallthrough)!; |
| 313 | /** |
| 314 | * Fallthrough of the inner optional should be a block with no |
| 315 | * instructions, terminating with Test($<temporary written to from |
| 316 | * StoreLocal>) |
| 317 | */ |
| 318 | if (testBlock.terminal.kind !== 'branch') { |
| 319 | return null; |
| 320 | } |
| 321 | /** |
| 322 | * Recurse into inner optional blocks to collect inner optional-chain |
| 323 | * expressions, regardless of whether we can match the outer one to a |
| 324 | * PropertyLoad. |
| 325 | */ |
| 326 | const innerOptional = traverseOptionalBlock( |
| 327 | maybeTest as TBasicBlock<OptionalTerminal>, |
| 328 | context, |
| 329 | testBlock.terminal.alternate, |
| 330 | ); |
| 331 | if (innerOptional == null) { |
| 332 | return null; |
| 333 | } |
| 334 | |
| 335 | /** |
| 336 | * Check that the inner optional is part of the same optional-chain as the |
| 337 | * outer one. This is not guaranteed, e.g. given a(c?.d)?.d |
| 338 | * ``` |
| 339 | * bb0: |
| 340 | * Optional test=bb1 |
| 341 | * bb1: |
| 342 | * $0 = LoadLocal a <-- part 1 of the outer optional-chaining base |
| 343 | * Optional test=bb2 fallth=bb5 <-- start of optional chain for c?.d |
| 344 | * bb2: |
| 345 | * ... (optional chain for c?.d) |
| 346 | * ... |
| 347 | * bb5: |
| 348 | * $1 = phi(c.d, undefined) <-- part 2 (continuation) of the outer optional-base |
| 349 | * $2 = Call $0($1) |
| 350 | * Branch $2 ... |
| 351 | * ``` |
| 352 | */ |
| 353 | if (testBlock.terminal.test.identifier.id !== innerOptional) { |
| 354 | return null; |
| 355 | } |
| 356 | |
| 357 | if (!optional.terminal.optional) { |
| 358 | /** |
| 359 | * If this is an non-optional load participating in an optional chain |
| 360 | * (e.g. loading the `c` property in `a?.b.c`), record that PropertyLoads |
| 361 | * from the inner optional value are hoistable. |
| 362 | */ |
| 363 | context.hoistableObjects.set( |
| 364 | optional.id, |
| 365 | assertNonNull(context.temporariesReadInOptional.get(innerOptional)), |
| 366 | ); |
| 367 | } |
| 368 | baseObject = assertNonNull( |
| 369 | context.temporariesReadInOptional.get(innerOptional), |
| 370 | ); |
| 371 | test = testBlock.terminal; |
| 372 | } else { |
| 373 | return null; |
| 374 | } |
| 375 | |
| 376 | if (test.alternate === outerAlternate) { |
| 377 | CompilerError.invariant(optional.instructions.length === 0, { |
| 378 | reason: |
| 379 | '[OptionalChainDeps] Unexpected instructions an inner optional block. ' + |
| 380 | 'This indicates that the compiler may be incorrectly concatenating two unrelated optional chains', |
| 381 | loc: optional.terminal.loc, |
| 382 | }); |
| 383 | } |
| 384 | const matchConsequentResult = matchOptionalTestBlock(test, context.blocks); |
| 385 | if (!matchConsequentResult) { |
| 386 | // Optional chain consequent is not hoistable e.g. a?.[computed()] |
| 387 | return null; |
| 388 | } |
| 389 | CompilerError.invariant( |
| 390 | matchConsequentResult.consequentGoto === optional.terminal.fallthrough, |
| 391 | { |
| 392 | reason: '[OptionalChainDeps] Unexpected optional goto-fallthrough', |
| 393 | description: `${matchConsequentResult.consequentGoto} != ${optional.terminal.fallthrough}`, |
| 394 | loc: optional.terminal.loc, |
| 395 | }, |
| 396 | ); |
| 397 | const load: ReactiveScopeDependency = { |
| 398 | identifier: baseObject.identifier, |
| 399 | reactive: baseObject.reactive, |
| 400 | path: [ |
| 401 | ...baseObject.path, |
| 402 | { |
| 403 | property: matchConsequentResult.property, |
| 404 | optional: optional.terminal.optional, |
| 405 | loc: matchConsequentResult.propertyLoadLoc, |
| 406 | }, |
| 407 | ], |
| 408 | loc: matchConsequentResult.propertyLoadLoc, |
| 409 | }; |
| 410 | context.processedInstrsInOptional.add(matchConsequentResult.storeLocalInstr); |
| 411 | context.processedInstrsInOptional.add(test); |
| 412 | context.temporariesReadInOptional.set( |
| 413 | matchConsequentResult.consequentId, |
| 414 | load, |
| 415 | ); |
| 416 | context.temporariesReadInOptional.set(matchConsequentResult.propertyId, load); |
| 417 | return matchConsequentResult.consequentId; |
| 418 | } |