| 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} from '..'; |
| 9 | import { |
| 10 | BlockId, |
| 11 | GeneratedSource, |
| 12 | HIRFunction, |
| 13 | MutableRange, |
| 14 | Place, |
| 15 | ReactiveScope, |
| 16 | ScopeId, |
| 17 | } from './HIR'; |
| 18 | import { |
| 19 | eachInstructionLValue, |
| 20 | eachInstructionOperand, |
| 21 | eachTerminalOperand, |
| 22 | terminalFallthrough, |
| 23 | } from './visitors'; |
| 24 | |
| 25 | /** |
| 26 | * This pass asserts that program blocks and scopes properly form a tree hierarchy |
| 27 | * with respect to block and scope ranges. In other words, two ranges must either |
| 28 | * disjoint or nested. |
| 29 | * |
| 30 | * ProgramBlockSubtree = subtree of basic blocks between a terminal and its fallthrough |
| 31 | * (e.g. continuation in the source AST). This spans every instruction contained within |
| 32 | * the source AST subtree representing the terminal. |
| 33 | * |
| 34 | * In this example, there is a single ProgramBlockSubtree, which spans instructions 1:5 |
| 35 | * ```js |
| 36 | * function Foo() { |
| 37 | * [0] a; |
| 38 | * [1] if (cond) { |
| 39 | * [2] b; |
| 40 | * [3] } else { |
| 41 | * [4] c; |
| 42 | * } |
| 43 | * [5] d; |
| 44 | * } |
| 45 | * ``` |
| 46 | * |
| 47 | * Scope = reactive scope whose range has been correctly aligned and merged. |
| 48 | */ |
| 49 | type Block = |
| 50 | | ({ |
| 51 | kind: 'ProgramBlockSubtree'; |
| 52 | id: BlockId; |
| 53 | } & MutableRange) |
| 54 | | ({ |
| 55 | kind: 'Scope'; |
| 56 | id: ScopeId; |
| 57 | } & MutableRange); |
| 58 | |
| 59 | export function getScopes(fn: HIRFunction): Set<ReactiveScope> { |
| 60 | const scopes: Set<ReactiveScope> = new Set(); |
| 61 | function visitPlace(place: Place): void { |
| 62 | const scope = place.identifier.scope; |
| 63 | if (scope != null) { |
| 64 | if (scope.range.start !== scope.range.end) { |
| 65 | scopes.add(scope); |
| 66 | } |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | for (const [, block] of fn.body.blocks) { |
| 71 | for (const instr of block.instructions) { |
| 72 | for (const operand of eachInstructionLValue(instr)) { |
| 73 | visitPlace(operand); |
| 74 | } |
| 75 | |
| 76 | for (const operand of eachInstructionOperand(instr)) { |
| 77 | visitPlace(operand); |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | for (const operand of eachTerminalOperand(block.terminal)) { |
| 82 | visitPlace(operand); |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | return scopes; |
| 87 | } |
| 88 | |
| 89 | /** |
| 90 | * Sort range in ascending order of start instruction, breaking ties |
| 91 | * with descending order of end instructions. For overlapping ranges, this |
| 92 | * always orders nested inner range after outer ranges which is identical |
| 93 | * to the ordering of a pre-order tree traversal. |
| 94 | * e.g. we order the following ranges to [0, 4], [0, 2], [5, 8] |
| 95 | * 0 ⌝ ⌝ |
| 96 | * 1 ⌟ | |
| 97 | * 2 | |
| 98 | * 3 ⌟ |
| 99 | * 4 |
| 100 | * 5 ⌝ |
| 101 | * 6 | |
| 102 | * 7 ⌟ |
| 103 | */ |
| 104 | export function rangePreOrderComparator( |
| 105 | a: MutableRange, |
| 106 | b: MutableRange, |
| 107 | ): number { |
| 108 | const startDiff = a.start - b.start; |
| 109 | if (startDiff !== 0) return startDiff; |
| 110 | return b.end - a.end; |
| 111 | } |
| 112 | |
| 113 | export function recursivelyTraverseItems<T, TContext>( |
| 114 | items: Array<T>, |
| 115 | getRange: (val: T) => MutableRange, |
| 116 | context: TContext, |
| 117 | enter: (val: T, context: TContext) => void, |
| 118 | exit: (val: T, context: TContext) => void, |
| 119 | ): void { |
| 120 | items.sort((a, b) => rangePreOrderComparator(getRange(a), getRange(b))); |
| 121 | let activeItems: Array<T> = []; |
| 122 | const ranges = items.map(getRange); |
| 123 | for (let i = 0; i < items.length; i++) { |
| 124 | const curr = items[i]; |
| 125 | const currRange = ranges[i]; |
| 126 | for (let i = activeItems.length - 1; i >= 0; i--) { |
| 127 | const maybeParent = activeItems[i]; |
| 128 | const maybeParentRange = getRange(maybeParent); |
| 129 | const disjoint = currRange.start >= maybeParentRange.end; |
| 130 | const nested = currRange.end <= maybeParentRange.end; |
| 131 | CompilerError.invariant(disjoint || nested, { |
| 132 | reason: 'Invalid nesting in program blocks or scopes', |
| 133 | description: `Items overlap but are not nested: ${maybeParentRange.start}:${maybeParentRange.end}(${currRange.start}:${currRange.end})`, |
| 134 | loc: GeneratedSource, |
| 135 | }); |
| 136 | if (disjoint) { |
| 137 | exit(maybeParent, context); |
| 138 | activeItems.length = i; |
| 139 | } else { |
| 140 | break; |
| 141 | } |
| 142 | } |
| 143 | enter(curr, context); |
| 144 | activeItems.push(curr); |
| 145 | } |
| 146 | |
| 147 | let curr = activeItems.pop(); |
| 148 | while (curr != null) { |
| 149 | exit(curr, context); |
| 150 | curr = activeItems.pop(); |
| 151 | } |
| 152 | } |
| 153 | const no_op: () => void = () => {}; |
| 154 | |
| 155 | export function assertValidBlockNesting(fn: HIRFunction): void { |
| 156 | const scopes = getScopes(fn); |
| 157 | |
| 158 | const blocks: Array<Block> = [...scopes].map(scope => ({ |
| 159 | kind: 'Scope', |
| 160 | id: scope.id, |
| 161 | ...scope.range, |
| 162 | })) as Array<Block>; |
| 163 | for (const [, block] of fn.body.blocks) { |
| 164 | const fallthroughId = terminalFallthrough(block.terminal); |
| 165 | if (fallthroughId != null) { |
| 166 | const fallthrough = fn.body.blocks.get(fallthroughId)!; |
| 167 | const end = fallthrough.instructions[0]?.id ?? fallthrough.terminal.id; |
| 168 | blocks.push({ |
| 169 | kind: 'ProgramBlockSubtree', |
| 170 | id: block.id, |
| 171 | start: block.terminal.id, |
| 172 | end, |
| 173 | }); |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | recursivelyTraverseItems(blocks, block => block, null, no_op, no_op); |
| 178 | } |