Key reordering does not preserve most components' states

[spiffytech]

Sandbox

If components in a list are reordered, the most of the moved components lose their state. I'm not totally sure what determines which ones keep/lose state, but some components that were rearranged definitely lose state.

[jeswin]

Good find!

For the benefit of other readers, let me summarize @spiffytech's example.

1. Create components m1, m2, m3, m4 and m5 each having the key prop defined.
2. Reverse the middle three components (to get m1, m4, m3, m2, m5). The reordering happens, but m3 and m2 are attached to newly created elements and lose state. m1, m4 and m5 use existing elements and retain state.

The reason for this is that the current algorithm only looks for elements starting from the previously located element. In this case, m4 was located at position = 4, and hence the search for m2 and m3 begins only from position = 5.

Which is probably ok if the element doesn't have a key. But in the case of key-ed elements, the search space should include previous elements as well perhaps. Again, if we do find such a node searching backwards, we'll have to detach and reattach it at the correct position.

@spiffytech What do you think?

[spiffytech]

I recommend the change be made. It's good to keep key/state behavior consistent and avoid surprising results, it seems strictly better than losing both the component and element state when key order changes, and it looks like it works out for other frameworks.

It makes sense to me that if I signal to forgo that the same component continues should be rendered, that its state would be preserved.

---

I'm having trouble finding documentation for the exact consequences of detaching elements. DOM spec (insert, remove) seems to defer to the HTML spec for what detaching/reattaching any given element will do. I think the effects might be case-by-case per element type?

I did some testing. <input> and <video> states appear unaffected by reattaching, while a YouTube <iframe> gets reinitialized.

My impression, reading around, is that folks aren't very concerned about node detachment impacting their app. I can't find people asking about specific problems stemming from it, except for folks wondering if any automatic cleanup happens when they permanently remove an element.

A quick skim of Morphdom's and Preact's (1, 2) update logic looks like they use replaceChild and insertBefore without doing anything special to compensate for detach/reattach side effects.

I created demos in Preact, React, and Vue, demonstrating that they all preserve component state when keys are reordered. So as far as I can tell, everyone is used to elements getting reattached and it doesn't seem to cause any significant problems.

[jeswin]

@spiffytech Thank for you the well thought out reply, and demos in three frameworks. I fully agree with what you're saying. I'll go ahead and make this change.

[jeswin]

@spiffytech This is a slightly trickier change. So this might take a couple of days more - I need to test more.

[spiffytech]

Sure thing 👍

[jeswin]

This is taking longer - requires a whole bunch of rewiring. I'm on it.

[spiffytech]

Cool, thanks for the update.

I realized - I was focused on preserving component state, but you mentioned element reordering, which seems important too. Can you clarify if the change you're working on works for just components, or also keyed non-component elements? I.e., an <input> with a key.

[jeswin]

Yes, the fix (whenever it's ready) should work for both. I'll add a test for that well.

[spiffytech]

Perfect - you da man!

[jeswin]

Sorry this is taking longer. It's quite a big change - hence moving very carefully.

[spiffytech]

Is there something I can do to help? If it's a big change I'd like to pitch in.

[jeswin]

Thanks, that'll be totally welcome! Let me put together a writeup first to explain the problem, and a possible solution.

[jeswin]

Let me quote the the problem again.

• Create components m1, m2, m3, m4 and m5 each having the key prop defined. Let's say, they are bound to elements e1, e2, e3, e4 and e5.
• Reverse the middle three components (to get m1, m4, m3, m2, m5). The reordering happens, but m3 and m2 are attached to newly created elements and lose state. m1, m4 and m5 use existing elements and retain state.

Reason:

• The current algorithm (implemented in findReplacementCandidateForComponent() and findReplacementCandidateForElement()) only looks for elements starting from the previously located element. In this case, m4 was located at position = 4 (e4), and hence the search for m2 and m3 begins only from position = 5 (e5).
• Now let me expand this is a bit more. When m4 in (in newly reversed order m1, m4, m3, m2, m5) is located at e4, forgo also removes nodes 2 and 3 (e2 and e3) from DOM. So they don't even exist in the DOM when we're searching for m2 and m3.

Possible Solution: I think it's ok to remove the nodes from DOM, but we should keep them around in a bucket of disconnected nodes. If an element does not show up, we should search this bucket of disconnected nodes as well. This bucket needs to be reset for every iteration of a parent element - because we need to search disconnected nodes only within the same parent.

It sounds like not a big deal (and maybe it isn't), but we'll have to pass this bucket around to every function on forgo. That's because the algo works in a very recursive manner. For instance, internalRender() -> renderArray() -> internalRender().

[spiffytech]

That sounds like it would work.

Would it make sense to attach the bucket to the element being iterated over? Is that advantageous vs passing a function parameter everywhere?

If we use the function parameter, maybe we could use a WeakMap to avoid needing to reset the bucket? If the code can be structured such that Forgo just drops all references to an element's bucket when it finishes processing an element, that's one less piece of bookkeeping to manage. With everything being recursive the actual memory freeing might not happen until the end of the render, but that's probably okay. But I haven't looked closely enough at the code to tell if there's a natural point to create the next bucket that's not also an obvious place to reset the old one.

[spiffytech]

Oh, no, the WeakMap might not work because discarded components need to be unmounted. Depending on when's best for that to happen we wouldn't be able to make bucket cleanup as implicit implicit action.

[jeswin]

Going to work on this. Don't have an ETA yet, though.

[jeswin]

But I haven't looked closely enough at the code to tell if there's a natural point to create the next bucket that's not also an obvious place to reset the old one.

The buckets need to be created everytime we process an element (such as a 'div') - since the bucket should contain child nodes which are temporarily removed from that parent (the 'div' or whatever). Once we're done with the element, the bucket goes out of scope (GC'ed like any other reference).

I don't see it so much as resetting the bucket, because we'll have a temp bucket every time we see an element. It's just an array we create, and it should go out of scope once we're done with the element.

[spiffytech]

Sounds good. Let me know if I can help.

[jeswin]

@spiffytech The master now passes the two tests for Component ordering and Element ordering. I am yet to push this out as a release given that it's a fairly significant change.

This super important fix is wholly thanks to you. Not just in the detailed bug reports and investigation efforts, but also the solution. I was going down a very complicated path, until you suggested that we could just hold the deletedNodes bucket in the element itself. Eureka! Now the element has a deletedNodes bucket into which deleted nodes go. These nodes are resurrected if later matched by an out of order keyed element. At that point we move the node back into the DOM, and take it off deletedNodes.

[jeswin]

It'll probably need more tweaking, so I'll take a day to make sure I didn't break stuff. So it's not ready to review (or even to try) yet.

[spiffytech]

Excellent! Thanks for working on it, I look forward to seeing it in action.

This super important fix is wholly thanks to you.

Thanks for the shout-out! I'm glad I've been helpful 🙂

[jeswin]

Published 2.2.0

[spiffytech]

At a first glance, v2.2.1 correctly retains state across key order changes (yay!). I've spotted a few issues (reproduction).

There's something weird in the repro: on the second button click, the final keyed element loses it's state. But only the second click - not the first, nor the third+.

I see an edge case: if a keyed stateful component returns a fragment containing stateful children, the children don't retain their state across rerenders. This makes sense given (2) described here, but it's unexpected as an application developer, since it amounts to a component only retaining partial state.

Additionally, there's a regression from Forgo 2.1: the final component in the repro retains its child's state in 2.1, but does not in 2.2.

[spiffytech]

I started writing failing tests to cover these cases. I pushed a commit that replicates reordering grandparents not being commutative.

I began updating the test to also catch the final grandchild changing state, but managed to trigger a runtime error with what looks like legal component code, so that's interesting.

[jeswin]

Thanks. The good news is that the code is more legible after the refactor, and hence the fixing shouldn't take as much time.

In hindsight, I should have just pushed it as an alpha.

[spiffytech]

Yeah, it's probably a good idea to start doing prerelease versions for the bigger / riskier changes.

[jeswin]

Thanks for the test. Working on it.

[spiffytech]

👍

I'd hoped to flesh out more tests for this but haven't been able to give it much attention this week.

[jeswin]

I've pushed a new commit which passes your test. Instead of doing an alpha, I've pushed a new version - because the previous one was buggy anyway. Going forward we'll do alphas.

The error was - when we resurrect nodes on account of being referenced by a keyed but re-ordered component, we need to bring back all the nodes associated with that. The mistake here was - I was resurrecting the first node, but when a component renders a fragment there might be more than one.

This was a tricky change - so I can't be sure there won't be more corner cases. :)

[spiffytech]

Everything looks good so far! I messed around a bit in the sandbox checking more complex cases, and haven't seen any problems. I'll reopen if I spot anything.

Instead of doing an alpha, I've pushed a new version - because the previous one was buggy anyway. Going forward we'll do alphas.

Sounds good.

The error was...

That makes total sense.

Thanks a bunch, I know you've been working hard on this.