| 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 | export type TreeContext = { |
| 64 | +id: number, |
| 65 | +overflow: string, |
| 66 | }; |
| 67 | |
| 68 | export const emptyTreeContext = { |
| 69 | id: 1, |
| 70 | overflow: '', |
| 71 | }; |
| 72 | |
| 73 | export function getTreeId(context: TreeContext): string { |
| 74 | const overflow = context.overflow; |
| 75 | const idWithLeadingBit = context.id; |
| 76 | const id = idWithLeadingBit & ~getLeadingBit(idWithLeadingBit); |
| 77 | return id.toString(32) + overflow; |
| 78 | } |
| 79 | |
| 80 | export function pushTreeContext( |
| 81 | baseContext: TreeContext, |
| 82 | totalChildren: number, |
| 83 | index: number, |
| 84 | ): TreeContext { |
| 85 | const baseIdWithLeadingBit = baseContext.id; |
| 86 | const baseOverflow = baseContext.overflow; |
| 87 | |
| 88 | // The leftmost 1 marks the end of the sequence, non-inclusive. It's not part |
| 89 | // of the id; we use it to account for leading 0s. |
| 90 | const baseLength = getBitLength(baseIdWithLeadingBit) - 1; |
| 91 | const baseId = baseIdWithLeadingBit & ~(1 << baseLength); |
| 92 | |
| 93 | const slot = index + 1; |
| 94 | const length = getBitLength(totalChildren) + baseLength; |
| 95 | |
| 96 | // 30 is the max length we can store without overflowing, taking into |
| 97 | // consideration the leading 1 we use to mark the end of the sequence. |
| 98 | if (length > 30) { |
| 99 | // We overflowed the bitwise-safe range. Fall back to slower algorithm. |
| 100 | // This branch assumes the length of the base id is greater than 5; it won't |
| 101 | // work for smaller ids, because you need 5 bits per character. |
| 102 | // |
| 103 | // We encode the id in multiple steps: first the base id, then the |
| 104 | // remaining digits. |
| 105 | // |
| 106 | // Each 5 bit sequence corresponds to a single base 32 character. So for |
| 107 | // example, if the current id is 23 bits long, we can convert 20 of those |
| 108 | // bits into a string of 4 characters, with 3 bits left over. |
| 109 | // |
| 110 | // First calculate how many bits in the base id represent a complete |
| 111 | // sequence of characters. |
| 112 | const numberOfOverflowBits = baseLength - (baseLength % 5); |
| 113 | |
| 114 | // Then create a bitmask that selects only those bits. |
| 115 | const newOverflowBits = (1 << numberOfOverflowBits) - 1; |
| 116 | |
| 117 | // Select the bits, and convert them to a base 32 string. |
| 118 | const newOverflow = (baseId & newOverflowBits).toString(32); |
| 119 | |
| 120 | // Now we can remove those bits from the base id. |
| 121 | const restOfBaseId = baseId >> numberOfOverflowBits; |
| 122 | const restOfBaseLength = baseLength - numberOfOverflowBits; |
| 123 | |
| 124 | // Finally, encode the rest of the bits using the normal algorithm. Because |
| 125 | // we made more room, this time it won't overflow. |
| 126 | const restOfLength = getBitLength(totalChildren) + restOfBaseLength; |
| 127 | const restOfNewBits = slot << restOfBaseLength; |
| 128 | const id = restOfNewBits | restOfBaseId; |
| 129 | const overflow = newOverflow + baseOverflow; |
| 130 | return { |
| 131 | id: (1 << restOfLength) | id, |
| 132 | overflow, |
| 133 | }; |
| 134 | } else { |
| 135 | // Normal path |
| 136 | const newBits = slot << baseLength; |
| 137 | const id = newBits | baseId; |
| 138 | const overflow = baseOverflow; |
| 139 | return { |
| 140 | id: (1 << length) | id, |
| 141 | overflow, |
| 142 | }; |
| 143 | } |
| 144 | } |
| 145 | |
| 146 | function getBitLength(number: number): number { |
| 147 | return 32 - clz32(number); |
| 148 | } |
| 149 | |
| 150 | function getLeadingBit(id: number) { |
| 151 | return 1 << (getBitLength(id) - 1); |
| 152 | } |
| 153 | |
| 154 | // TODO: Math.clz32 is supported in Node 12+. Maybe we can drop the fallback. |
| 155 | const clz32 = Math.clz32 ? Math.clz32 : clz32Fallback; |
| 156 | |
| 157 | // Count leading zeros. |
| 158 | // Based on: |
| 159 | // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32 |
| 160 | const log = Math.log; |
| 161 | const LN2 = Math.LN2; |
| 162 | function clz32Fallback(x: number): number { |
| 163 | const asUint = x >>> 0; |
| 164 | if (asUint === 0) { |
| 165 | return 32; |
| 166 | } |
| 167 | return (31 - ((log(asUint) / LN2) | 0)) | 0; |
| 168 | } |