Child reconciliation algorithm question

[dmjio]

trafficstars

@localvoid, hello! :)

Thank you for taking the time to go into such detail about how kivi's diffing algorithm works in syncChildren. I just had a few questions of clarification on some of the cases that you've outlined in your comments.

Most cases make perfect sense to me, but I had a question about one case that wasn't mentioned.

So in review,

--> [ a d b c ] <--
--> [ a b d c ] <--

Here a and c are the same so we keep drilling into the list both ways. Makes sense. We increment first indices, and decrement last indices, on both lists.

--> [ d b ] <--
--> [ b d ] <--

Here we can flip-flop d and b. Still makes sense. We do insertBefore trick and swap them.

--> [ e j ] <--
--> [ k r ] <--

Nothing matches, so we escape into special case, and do more complicated things. Still makes sense. Do special increasing subsequence and track if nodes have been moved, etc.

Now, this case... What case does this fall into?

    [ a b ] <--
--> [ b d ]

Is there a special way to handle this? Or does it fall into the above case (where nothing matches) ?

Thanks again :)

[localvoid]

This is the edge case when it will use more DOM ops than it is necessary because of prefix/suffix optimization, I've added a note about this case in ivi sources: https://github.com/ivijs/ivi/blob/dd4f3f3c92e1c758f5e3df2e803604bc071ce9cd/src/vdom/implementation.ts#L1651-L1652

It should go through this code path:

• prefix/suffix phase, checking edges. Move node "b": https://github.com/localvoid/kivi/blob/26eae1043efb9cc4ba7e54c1c4ab30389a669149/lib/vnode.ts#L1572-L1589
• complicated phase on [a] => [d]. Find all removed/inserted nodes and detect if someone were moved: https://github.com/localvoid/kivi/blob/26eae1043efb9cc4ba7e54c1c4ab30389a669149/lib/vnode.ts#L1628-L1664
• Remove node "a": https://github.com/localvoid/kivi/blob/26eae1043efb9cc4ba7e54c1c4ab30389a669149/lib/vnode.ts#L1706-L1713
• Insert node "d": https://github.com/localvoid/kivi/blob/26eae1043efb9cc4ba7e54c1c4ab30389a669149/lib/vnode.ts#L1738-L1748

It is possible to slightly optimize this use case when one DOM node is left after prefix/suffix phase, but I am not sure if it is worth it: https://github.com/ivijs/ivi/blob/dd4f3f3c92e1c758f5e3df2e803604bc071ce9cd/src/vdom/implementation.ts#L1767-L1768

ivi has a slightly modified version of this algo. It can handle use cases with implicit positional indexing, when nodes without explicit keys automatically assigned with implicit keys to support code patterns like this <div>{condition ? <ComponentA> : null}<ComponentA></div>. Most vdom libraries doesn't handle such use cases, and instead of removing/inserting first ComponentA when condition is changing, they will remove/insert the second one, and internal state of this components will be incorrect. Here is an example when vue2 loses internal state, because it doesn't support this edge case: https://jsfiddle.net/4ppdfyy8/