| 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 | * @flow |
| 8 | */ |
| 9 | |
| 10 | // Ids are base 32 strings whose binary representation corresponds to the |
| 11 | // position of a node in a tree. |
| 12 | |
| 13 | // Every time the tree forks into multiple children, we add additional bits to |
| 14 | // the left of the sequence that represent the position of the child within the |
| 15 | // current level of children. |
| 16 | // |
| 17 | // 00101 00010001011010101 |
| 18 | // ╰─┬─╯ ╰───────┬───────╯ |
| 19 | // Fork 5 of 20 Parent id |
| 20 | // |
| 21 | // The leading 0s are important. In the above example, you only need 3 bits to |
| 22 | // represent slot 5. However, you need 5 bits to represent all the forks at |
| 23 | // the current level, so we must account for the empty bits at the end. |
| 24 | // |
| 25 | // For this same reason, slots are 1-indexed instead of 0-indexed. Otherwise, |
| 26 | // the zeroth id at a level would be indistinguishable from its parent. |
| 27 | // |
| 28 | // If a node has only one child, and does not materialize an id (i.e. does not |
| 29 | // contain a useId hook), then we don't need to allocate any space in the |
| 30 | // sequence. It's treated as a transparent indirection. For example, these two |
| 31 | // trees produce the same ids: |
| 32 | // |
| 33 | // <> <> |
| 34 | // <Indirection> <A /> |
| 35 | // <A /> <B /> |
| 36 | // </Indirection> </> |
| 37 | // <B /> |
| 38 | // </> |
| 39 | // |
| 40 | // However, we cannot skip any node that materializes an id. Otherwise, a parent |
| 41 | // id that does not fork would be indistinguishable from its child id. For |
| 42 | // example, this tree does not fork, but the parent and child must have |
| 43 | // different ids. |
| 44 | // |
| 45 | // <Parent> |
| 46 | // <Child /> |
| 47 | // </Parent> |
| 48 | // |
| 49 | // To handle this scenario, every time we materialize an id, we allocate a |
| 50 | // new level with a single slot. You can think of this as a fork with only one |
| 51 | // prong, or an array of children with length 1. |
| 52 | // |
| 53 | // It's possible for the size of the sequence to exceed 32 bits, the max |
| 54 | // size for bitwise operations. When this happens, we make more room by |
| 55 | // converting the right part of the id to a string and storing it in an overflow |
| 56 | // variable. We use a base 32 string representation, because 32 is the largest |
| 57 | // power of 2 that is supported by toString(). We want the base to be large so |
| 58 | // that the resulting ids are compact, and we want the base to be a power of 2 |
| 59 | // because every log2(base) bits corresponds to a single character, i.e. every |
| 60 | // log2(32) = 5 bits. That means we can lop bits off the end 5 at a time without |
| 61 | // affecting the final result. |
| 62 | |
| 63 | import type {Fiber} from 'react-reconciler/src/ReactInternalTypes'; |
| 64 | |
| 65 | import {getIsHydrating} from './ReactFiberHydrationContext'; |
| 66 | import {clz32} from './clz32'; |
| 67 | import {Forked, NoFlags} from './ReactFiberFlags'; |
| 68 | |
| 69 | export type TreeContext = { |
| 70 | id: number, |
| 71 | overflow: string, |
| 72 | }; |
| 73 | |
| 74 | // TODO: Use the unified fiber stack module instead of this local one? |
| 75 | // Intentionally not using it yet to derisk the initial implementation, because |
| 76 | // the way we push/pop these values is a bit unusual. If there's a mistake, I'd |
| 77 | // rather the ids be wrong than crash the whole reconciler. |
| 78 | const forkStack: Array<any> = []; |
| 79 | let forkStackIndex: number = 0; |
| 80 | let treeForkProvider: Fiber | null = null; |
| 81 | let treeForkCount: number = 0; |
| 82 | |
| 83 | const idStack: Array<any> = []; |
| 84 | let idStackIndex: number = 0; |
| 85 | let treeContextProvider: Fiber | null = null; |
| 86 | let treeContextId: number = 1; |
| 87 | let treeContextOverflow: string = ''; |
| 88 | |
| 89 | export function isForkedChild(workInProgress: Fiber): boolean { |
| 90 | warnIfNotHydrating(); |
| 91 | return (workInProgress.flags & Forked) !== NoFlags; |
| 92 | } |
| 93 | |
| 94 | export function getForksAtLevel(workInProgress: Fiber): number { |
| 95 | warnIfNotHydrating(); |
| 96 | return treeForkCount; |
| 97 | } |
| 98 | |
| 99 | export function getTreeId(): string { |
| 100 | const overflow = treeContextOverflow; |
| 101 | const idWithLeadingBit = treeContextId; |
| 102 | const id = idWithLeadingBit & ~getLeadingBit(idWithLeadingBit); |
| 103 | return id.toString(32) + overflow; |
| 104 | } |
| 105 | |
| 106 | export function pushTreeFork( |
| 107 | workInProgress: Fiber, |
| 108 | totalChildren: number, |
| 109 | ): void { |
| 110 | // This is called right after we reconcile an array (or iterator) of child |
| 111 | // fibers, because that's the only place where we know how many children in |
| 112 | // the whole set without doing extra work later, or storing addtional |
| 113 | // information on the fiber. |
| 114 | // |
| 115 | // That's why this function is separate from pushTreeId — it's called during |
| 116 | // the render phase of the fork parent, not the child, which is where we push |
| 117 | // the other context values. |
| 118 | // |
| 119 | // In the Fizz implementation this is much simpler because the child is |
| 120 | // rendered in the same callstack as the parent. |
| 121 | // |
| 122 | // It might be better to just add a `forks` field to the Fiber type. It would |
| 123 | // make this module simpler. |
| 124 | |
| 125 | warnIfNotHydrating(); |
| 126 | |
| 127 | forkStack[forkStackIndex++] = treeForkCount; |
| 128 | forkStack[forkStackIndex++] = treeForkProvider; |
| 129 | |
| 130 | treeForkProvider = workInProgress; |
| 131 | treeForkCount = totalChildren; |
| 132 | } |
| 133 | |
| 134 | export function pushTreeId( |
| 135 | workInProgress: Fiber, |
| 136 | totalChildren: number, |
| 137 | index: number, |
| 138 | ) { |
| 139 | warnIfNotHydrating(); |
| 140 | |
| 141 | idStack[idStackIndex++] = treeContextId; |
| 142 | idStack[idStackIndex++] = treeContextOverflow; |
| 143 | idStack[idStackIndex++] = treeContextProvider; |
| 144 | |
| 145 | treeContextProvider = workInProgress; |
| 146 | |
| 147 | const baseIdWithLeadingBit = treeContextId; |
| 148 | const baseOverflow = treeContextOverflow; |
| 149 | |
| 150 | // The leftmost 1 marks the end of the sequence, non-inclusive. It's not part |
| 151 | // of the id; we use it to account for leading 0s. |
| 152 | const baseLength = getBitLength(baseIdWithLeadingBit) - 1; |
| 153 | const baseId = baseIdWithLeadingBit & ~(1 << baseLength); |
| 154 | |
| 155 | const slot = index + 1; |
| 156 | const length = getBitLength(totalChildren) + baseLength; |
| 157 | |
| 158 | // 30 is the max length we can store without overflowing, taking into |
| 159 | // consideration the leading 1 we use to mark the end of the sequence. |
| 160 | if (length > 30) { |
| 161 | // We overflowed the bitwise-safe range. Fall back to slower algorithm. |
| 162 | // This branch assumes the length of the base id is greater than 5; it won't |
| 163 | // work for smaller ids, because you need 5 bits per character. |
| 164 | // |
| 165 | // We encode the id in multiple steps: first the base id, then the |
| 166 | // remaining digits. |
| 167 | // |
| 168 | // Each 5 bit sequence corresponds to a single base 32 character. So for |
| 169 | // example, if the current id is 23 bits long, we can convert 20 of those |
| 170 | // bits into a string of 4 characters, with 3 bits left over. |
| 171 | // |
| 172 | // First calculate how many bits in the base id represent a complete |
| 173 | // sequence of characters. |
| 174 | const numberOfOverflowBits = baseLength - (baseLength % 5); |
| 175 | |
| 176 | // Then create a bitmask that selects only those bits. |
| 177 | const newOverflowBits = (1 << numberOfOverflowBits) - 1; |
| 178 | |
| 179 | // Select the bits, and convert them to a base 32 string. |
| 180 | const newOverflow = (baseId & newOverflowBits).toString(32); |
| 181 | |
| 182 | // Now we can remove those bits from the base id. |
| 183 | const restOfBaseId = baseId >> numberOfOverflowBits; |
| 184 | const restOfBaseLength = baseLength - numberOfOverflowBits; |
| 185 | |
| 186 | // Finally, encode the rest of the bits using the normal algorithm. Because |
| 187 | // we made more room, this time it won't overflow. |
| 188 | const restOfLength = getBitLength(totalChildren) + restOfBaseLength; |
| 189 | const restOfNewBits = slot << restOfBaseLength; |
| 190 | const id = restOfNewBits | restOfBaseId; |
| 191 | const overflow = newOverflow + baseOverflow; |
| 192 | |
| 193 | treeContextId = (1 << restOfLength) | id; |
| 194 | treeContextOverflow = overflow; |
| 195 | } else { |
| 196 | // Normal path |
| 197 | const newBits = slot << baseLength; |
| 198 | const id = newBits | baseId; |
| 199 | const overflow = baseOverflow; |
| 200 | |
| 201 | treeContextId = (1 << length) | id; |
| 202 | treeContextOverflow = overflow; |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | export function pushMaterializedTreeId(workInProgress: Fiber) { |
| 207 | warnIfNotHydrating(); |
| 208 | |
| 209 | // This component materialized an id. This will affect any ids that appear |
| 210 | // in its children. |
| 211 | const returnFiber = workInProgress.return; |
| 212 | if (returnFiber !== null) { |
| 213 | const numberOfForks = 1; |
| 214 | const slotIndex = 0; |
| 215 | pushTreeFork(workInProgress, numberOfForks); |
| 216 | pushTreeId(workInProgress, numberOfForks, slotIndex); |
| 217 | } |
| 218 | } |
| 219 | |
| 220 | function getBitLength(number: number): number { |
| 221 | return 32 - clz32(number); |
| 222 | } |
| 223 | |
| 224 | function getLeadingBit(id: number) { |
| 225 | return 1 << (getBitLength(id) - 1); |
| 226 | } |
| 227 | |
| 228 | export function popTreeContext(workInProgress: Fiber) { |
| 229 | // Restore the previous values. |
| 230 | |
| 231 | // This is a bit more complicated than other context-like modules in Fiber |
| 232 | // because the same Fiber may appear on the stack multiple times and for |
| 233 | // different reasons. We have to keep popping until the work-in-progress is |
| 234 | // no longer at the top of the stack. |
| 235 | |
| 236 | while (workInProgress === treeForkProvider) { |
| 237 | treeForkProvider = forkStack[--forkStackIndex]; |
| 238 | forkStack[forkStackIndex] = null; |
| 239 | treeForkCount = forkStack[--forkStackIndex]; |
| 240 | forkStack[forkStackIndex] = null; |
| 241 | } |
| 242 | |
| 243 | while (workInProgress === treeContextProvider) { |
| 244 | treeContextProvider = idStack[--idStackIndex]; |
| 245 | idStack[idStackIndex] = null; |
| 246 | treeContextOverflow = idStack[--idStackIndex]; |
| 247 | idStack[idStackIndex] = null; |
| 248 | treeContextId = idStack[--idStackIndex]; |
| 249 | idStack[idStackIndex] = null; |
| 250 | } |
| 251 | } |
| 252 | |
| 253 | export function getSuspendedTreeContext(): TreeContext | null { |
| 254 | warnIfNotHydrating(); |
| 255 | if (treeContextProvider !== null) { |
| 256 | return { |
| 257 | id: treeContextId, |
| 258 | overflow: treeContextOverflow, |
| 259 | }; |
| 260 | } else { |
| 261 | return null; |
| 262 | } |
| 263 | } |
| 264 | |
| 265 | export function restoreSuspendedTreeContext( |
| 266 | workInProgress: Fiber, |
| 267 | suspendedContext: TreeContext, |
| 268 | ) { |
| 269 | warnIfNotHydrating(); |
| 270 | |
| 271 | idStack[idStackIndex++] = treeContextId; |
| 272 | idStack[idStackIndex++] = treeContextOverflow; |
| 273 | idStack[idStackIndex++] = treeContextProvider; |
| 274 | |
| 275 | treeContextId = suspendedContext.id; |
| 276 | treeContextOverflow = suspendedContext.overflow; |
| 277 | treeContextProvider = workInProgress; |
| 278 | } |
| 279 | |
| 280 | function warnIfNotHydrating() { |
| 281 | if (__DEV__) { |
| 282 | if (!getIsHydrating()) { |
| 283 | console.error( |
| 284 | 'Expected to be hydrating. This is a bug in React. Please file ' + |
| 285 | 'an issue.', |
| 286 | ); |
| 287 | } |
| 288 | } |
| 289 | } |