身份生成算法
身份 id 是 32 進制的字符串,其二進制表示對應樹中節點的位置。
每次樹分叉成多個子節點時,我們都會在序列的左側添加額外的位數,表示子節點在當前子節點層級中的位置。
00101 00010001011010101
╰─┬─╯ ╰───────┬───────╯
Fork 5 of 20 Parent id
這里我們使用了兩個前置 0 位。如果只考慮當前的子節點,我們使用 101 就可以了,但是要表達當前層級所有的子節點,三位就不夠用。因此需要 5 位。
出于同樣的原因,slots 是 1-indexed 而不是 0-indexed 。否則就無法區分該層級第 0 個子節點與父節點。
如果一個節點只有一個子節點,并且沒有具體化的 id,聲明時沒有包含 useId hook。那么我們不需要在序列中分配任何空間。例如這兩顆數會產生相同的 id:
<> <>
<Indirection> <A />
<A /> <B />
</Indirection> </>
<B />
</>
為了處理這種情況,每次我們生成一個 id 時,都會分配一個一個新的層級。當然這個層級就只有一個節點「長度為 1 的數組」。
最后,序列的大小可能會超出 32 位,發生這種情況時,我們通過將 id 的右側部分轉換為字符串并將其存儲在溢出變量中。之所以使用 32 位字符串,是因為 32 是 toString() 支持的 2 的最大冪數。這樣基數足夠大就能夠得到緊湊的 id 序列,并且我們希望基數是 2 的冪,因為每個 log2(base) 對應一個字符,也就是 log2(32) = 5 bits = 1 ,這樣意味著我們可以在不影響最終結果的情況下刪除末尾 5 的位。