Feature: move internal node nesting model to doubly linked lists

[trueadm]

Today, Lexical nodes are nested using arrays. This means that ElementNode references an array of child node keys. However, we can improve performance by switching away from arrays, and to using doubly linked lists. This would mean

• We remove ElementNode.__children
• We add ElementNode.__first, which is either NodeKey or null.
• We add ElementNode.__last, which is either NodeKey or null.
• We add ElementNode.__size, which is number. Avoiding the need to do O(n) lookups to find the amount of children in the element.
• We add LexicalNode._prev, which is either NodeKey or null.
• We add LexicalNode._next, which is either NodeKey or null.

When we add/remove a node, we'll need to make sure to update the linked list of both adjacent siblings (__prev and __next). Additionally, if the node is the first or last node of its parent, we'll also have to update the parent __size, __first and/or __last. We can remove the logic we have for marking siblings dirty, as we'll do that organically from using linked lists.

[fantactuka]

Should mark it as a breaking change since state format will be changed

[trueadm]

I think we probably want to introduce this to start with, in addition to the existing API. Have them both there, then switch, then remove the old in v0.3. So we'll be duplicating work for a short-time, to ensure backwards compatibility.

[acywatson]

Work in progress in #2044

As a general FYI, we reprioritized this behind the JSON serialization changes, since those were important to insulate users against breaking changes to our internal node schemas (like re-implementing the state to use linked lists 😄 )

[GermanJablo]

I was planning to suggest/work on this later, but I see you have already noticed this opportunity for improvement as well.

Just an observation. My intuition tells me that single linked list will be even more performant than double linked list. Most operations, like rendering, need only the next sibling. In case there are a few occasional operations that need the previous sibling, I don't think such savings in operations outweigh duplicating every other operation that a simple linked list model would require.

[fantactuka]

InsertBefore and delete would be linear vs constant with dll. And delete is one of (if not the most) used op since whenever node is moved around it's deleted from current parent first

[GermanJablo]

delete is a method of LexicalNode or ElementNode? Could you tell me where in the code it is? I'm not seeing it

[acywatson]

delete is a method of LexicalNode or ElementNode? Could you tell me where in the code it is? I'm not seeing it

It’s actually called “remove”

https://github.com/facebook/lexical/pull/2044/files#diff-eae9d8a8a05fee2910d2082d36f6f1683ba3632596e8d9cab326ef1fb0651065R660

[acywatson]

@trueadm did this!