Unexpected reordering after keyed removal

[mindplay-dk]

Per this example using current unstable picodom @2.0.0

https://jsfiddle.net/4eunk2um/

Click to remove elements from the list, and note how the removed element always ends up at the bottom of the range - because it doesn't get destroyed until 2 seconds later.

Keyed updates presumably exist, for one, so you can do this sort of thing?

[jorgebucaran]

@mindplay-dk It seems this demos the problem you were having with @zaceno's transitions or am I looking at something else?

[jorgebucaran]

Nevermind, I see the elements are correctly removed, but I admit there's something funny going on.

[zaceno]

@mindplay-dk @JorgeBucaran this is just how the algorithm works. We can't leave the to-be-removed-elements in their original place, because that messes up the indexes mapping vdom to DOM. So the elements go to the bottom of the list, outside the range of the vdom.

I don't think I'd consider it a bug so much as the only reasonable way (I can think of) to handle delayed element removal. More like a "known limitation"

Incidentally, this behavior is precisely the reason I have to do position tracking in hyperapp-transitions.

[mindplay-dk]

We can't leave the to-be-removed-elements in their original place, because that messes up the indexes mapping vdom to DOM.

I think maybe we just discovered why some libs (petit-dom, snabbdom, etc.) implement diffing and patching in two separate passes.

To me, this is by no means a "limitation" - it makes onremove not useful for the one thing I'd want to use it for: transitions.

[jorgebucaran]

@mindplay-dk What do you suggest we do?

[mindplay-dk]

One option is promises, like I suggested earlier - so that you can actually know when an update has finished. Not completely convinced that would even solve it necessarily though, since another update could be triggered indirectly by another DOM event (click, input, etc.) before the update is complete - you'd have to control the updates at a higher level to address that, e.g. something like snabbdom's patch(container, vnode) which "cheats" by injecting historical state into the vnode, which seems really dirty; it wouldn't be my preferred approach... there is surely another way to factor the same functionality though, without relying on side-effects, but anyhow...

I'm not sure there are any simple answers here.

Perhaps supporting an onremove event is kind of the problem in the first place - encouraging you to defer the actual destruction of the element appears to be the root cause of this issue. I mean, you could argue that we're enabling deferred removals, but the library actually doesn't really support deferred removals - it doesn't really work, just leads to broken UI.

Arguably, for things like animation, there are likely better/simpler/more explicit ways to achieve animation, besides intercepting the removal of an element from the DOM. Like, what does removal mean? If removal means removing the element from the DOM, clearly that's the wrong time to decide you're not ready to remove the element from the DOM, because the DOM and the VNode model ends up out of sync.

You could argue you just shouldn't remove elements from the VDOM before you're ready to remove them from the DOM. On the other hand, it's terribly convenient, because removals are usually in response to changes that have already happened in the model, and (with e.g. the SAM pattern) that means, by the next render, you no longer have the information that was removed from your model.

Sorry for the stream of consciousness here, but... I think the bottom line is, either we support a feature like this and make it work, or we remove a partial feature that isn't really going to be useful.

I'd really like to see it work of course.

Well, here's one idea, maybe... what if you passed the resolve function of a Promise to the onremove handler, and that way made it responsible for signaling back to the framework when it's ready for the actual element removal? Okay, so that's not really different from what we're doing with the remove callback now, but, if at the same time, you were to attach this Promise to the VNode itself, so that, during the next call to patch, you could look at the old VNode, see if it's carrying one of these previously-issues promises, and check if it's been resolved - and if it hasn't, we'll consider the old VNode as still valid; let it participate in that update exactly as if it were still in the list of new VNodes, at the location we're currently processing in the old list of VNodes. I don't know, would that work??

[jorgebucaran]

What if we make onremove function like ondestroy, which is actually necessary and we can implement (@4lejandrito already did!) and get rid of the current onremove behavior. For animation I would prefer CSS.

[mindplay-dk]

For animation I would prefer CSS

In theory, so would I - in practice, as said, the data as already been removed from your model, unless you build your model with something like an array of elements_being_removed, which would just be tremendously awkward. Animation is a detail I don't want to concern my model with.

The promise idea might work... this part:

      var oldKey = getKey(oldChild)
      if (keyed[oldKey]) {
        i++
        continue
      }

Here we skip to the next old index, potentially skipping an element that's actually still alive, right?

So, something like this:

      var oldKey = getKey(oldChild)
      if (keyed[oldKey]) {
        i++
        continue
      } else if (oldChild.is_being_removed) {
        keyed[oldKey] = oldChild
        oldKeyed[oldKey] = [oldElement, oldChild]
        i++
        continue
      }

That is, if we encounter an old keyed node, and it's not present in the keys of the new nodes, if it's been flagged as is_being_removed, we make it carry over to the next update even though it's missing. The Promise, when resolved, will clear the flag.

Obviously this code is wrong/incomplete, we'd also have to actually inject the missing VNode from old nodes into new nodes to make sure it carries over not only for the next update, but for every future update, until the flag is cleared.

The point is, by the first update where we find an old keyed node has been removed, we still have the order information in the old list of nodes - that hasn't been lost yet! We just need to somehow make that information carry over from this update to future updates, until we find that the actual removal has happened.

(we don't necessarily need promises for that, we could also just check if the DOM element we encounter still has a parent node - if it doesn't, it's been removed.)

[leeoniya]

i'm not too familiar with the picodom's reconciler, but all too familiar with these implementation details. domvm has a 2-pass reconciler:

1. oldVtree <-> newVtree is resolved and attrs/textContent is patched, dom element is re-linked to new vtree
2. the dom reconciler reorders, inserts and removes children

in part 2, if any element must be removed and willRemove or willUnmount hooks return a Promise, it hooks up a deferred removal and sets a ._dead = true flag so that any followup redraws can skip over it in part 2 again.

this is certainly not the whole story, so i dunno if that helps.

[mindplay-dk]

For starters, I've modified the onremove test-case (#69) to provide a clear illustration of the problem.

This modified test-case defers the removal by hoisting the remove callback to the test-scope - then makes assertions after patching but before invoking the deferred/hoisted remove callback.

In my opinion, we should get this working before attempting to add the ondestroy feature - these life-cycle events are closely related, and likely fixing the issue with onremove will affect the dispatch of ondestroy handlers. Also, just, one thing at a time, right? ;-)

I don't have a concrete idea how to fix this, just the clues posted above, so I will leave it here for now, in the hopes that someone else can figure it out maybe. The test should help, right? :-)

[zaceno]

I think something like you guys suggested, passing forward "dead" nodes at their current index, might do just the trick. And now I'm curious to investigate it (no promises though, I'm a bit busy at the moment)

I feel like I've kind of been the "transistions" guy in the hyperapp/picodom sphere. And yet this hasn't been a pressing issue for me. That's because I've also been doing FLIP animations, which requires movement/layout tracking the elements. And once you've already paid that price, you get properly laid out remove transitions for almost free.

But if you don't care about FLIP animations then I agree that layout tracking & compensation is too steep a price to pay for such a simple thing as a remove transition. So I'd like to see this solved.

Still, I'm not familiar with any other vdom engines, so I'm still wondering if we're sure this is not also a problem in for example snabbdom? (@leeonya, you seem to suggest this issue is solved in vmdom?)

At least... I know Vue is based on snabbdom, but it ships with its own transitions library, which might indicate transitions are not so straightforward there either...

@mindplay-dk have you by chance checked (like with a similar jsfiddle) if any other vdom engines have the desired behavior?

[leeoniya]

@zaceno https://github.com/leeoniya/domvm/issues/159 & https://jsfiddle.net/cup40vu7/

[jorgebucaran]

What does preact do or how did they solve this?

[jorgebucaran]

@mindplay-dk By the way, I forgot to ask probably the most important question. What's the desired result? Like, how would you expect the animation to play out?

[zaceno]

I would assume it's that the elements keep their current place in the list until they're actually removed. Like in @leeoniya s example with vmdom

... but @mindplay-dk should answer for himself of course ;)

[mindplay-dk]

What @zaceno said :-)

[jorgebucaran]

It's hard to understand @leeoniya's example, I mean not his code (well, that's another story haha), but the concept (what we are talking about). I'll try looking at it again.

@mindplay-dk So, you want the element to remain on the DOM, but you changed the state and the DOM is built according to the state. 🤔

What about keeping transition information in the state?

[zaceno]

@JorgeBucaran not just remain in the dom, but remain at the same place in the dom (so they don't jump to the bottom before animating out)

[mindplay-dk]

So, you want the element to remain on the DOM, but you changed the state and the DOM is built according to the state

It is, but not according to how onremove supposedly works.

So either the specification is wrong, in which case onremove likely shouldn't exist at all - or the specification is right, and onremove needs to meet the spec.

I'd argue the latter - there's a reason we have the VDOM as an intermediary before the real DOM, and enhancing the life-cycle vs that supported by DOM itself, is arguably one of the more useful advantages that VDOM provides over traditional DOM.

If we don't take advantage of having a VDOM at our disposal, why do we have it at all? It's one reason I actually prefer the VDOM approach over libraries of late using patching strategies that directly patch the DOM with no intermediary model at all.

We could make do with just an ondestroy, but without the enhanced life-cycle, as with plain DOM, things like animation would not be directly possible without substantially displacing picodom and pushing that responsibility elsewhere by some other mechanism. The VDOM is absolutely suitable for this feature, and I hope we're not looking for excuses to forego this feature because it's hard? ;-)

[mindplay-dk]

(I'd love to help solving this problem, I just don't know when I'll have time.)

[jorgebucaran]

@mindplay-dk I am not looking for excuses to forego this feature, but I first need to understand what we want. 😄

[leeoniya]

in fewest words: during any redraw, the lib should never move elements that have been queued for removal by a prior ondestroy/promise.

the code in the jsfiddle i linked wasn't mine, heh :)

[zaceno]

@JorgeBucaran what leeoniya said.

You are aware, of course, that when we see that a keyed node is removed from the vdom, and we go to see if there's an onremove handler to call.

Then if there is we don't immediately remove the element. So the element is still in the dom for a while - but where in the dom? At the bottom of the sibling list.

The effect of that is, if you naively use a css-transition to fade out the element, the element will first skip to the bottom of the list, and from there start fading out.

What @mindplay-dk is asking for, is that the element fades out from it's original position.

[zaceno]

I deleted my previous comment of why I want to keep the current behavior, because just after posting I realized a solution to the thing I was saying would be impossible with @mindplay-dk 's suggested behavior. 🤦‍♂️

[mindplay-dk]

@zaceno right on the money! 😄

@JorgeBucaran what he said 😉

[mindplay-dk]

I attempted a fix but I'm out of time, and I had to give up.

I can provide some clues as to what won't work.

My idea was to flag the old node for preservation inside removeElement:

function removeElement(parent, child, element) {
  var props = child.props

  if (
    props &&
    props.onremove &&
    typeof (props = props.onremove(element)) === "function"
  ) {
    child.preserve = true
    props(function () {
      child.preserve = false
      remove()
    })
  } else {
    remove()
  }

  function remove() {
    parent.removeChild(element)
  }
}

Note that I change the function signature from (parent, element, childProps) to (parent, child, element) so as to get access to the VNode.

Inside the main loop I figured I'd then splice the preserved node back into the list of new nodes:

    while (j < len) {
      var oldElement = oldElements[i]
      var oldChild = oldNode.children[i]
      var newChild = node.children[j]

      if (oldChild && oldChild.preserve) {
        node.children.splice(j, 0, oldChild)
        i++
        len++
        continue
      }

From doing a lot of console.log() statements to try to understand the order of events, I can say though, this approach is not going to work, because, by the time we flag the node for preservation, it has in fact already been removed.

I think what needs to happen is we must somehow preserve the node as soon as we encounter it - like that means removeNode needs to return a flag indicating whether or not the node in question may actually be removed.

function removeElement(parent, child, element) {
  var props = child.props

  if (
    props &&
    props.onremove &&
    !child.destroying &&
    typeof (props = props.onremove(element)) === "function"
  ) {
    child.destroying = true // flag to avoid triggerin onremove handler again
    props(function () {
      child.destroy = true // flag for actual destruction in main loop
      remove()
    })
    return false // not removed yet
  } else {
    remove()
    return true // directly removed
  }

  function remove() {
    parent.removeChild(element)
  }
}

Unfortunately there are three different calls to removeElement which may all need to act differently depending on whether or not the node was actually removed.

Note that we can't simply pass the list of new nodes to this function, because the len in the main loop will also change if we carry over an old removed node.

That's all I got, and I won't get to this again until next week most likely, so...

[zaceno]

@mindplay-dk @JorgeBucaran yes I made a brief attempt at it too, but I think this requires a bit of a rethink of the algorithm, at least for me. Unfortunately I don't quite have the time either, at the moment. But IIRC Jorge was planning a makeover anyway, to optimize it somewhat. Maybe look into this at the same time?

[jorgebucaran]

@zaceno Maybe look into this at the same time?

If this is not resolved by then, I'll definitely look into it when I get to rewrite patch. Maybe in 2 or 3 months if I can use my time well. I really wish it could be sooner! 😞

[mindplay-dk]

@JorgeBucaran this is the only remaining major issue for me, but it's non-blocking - really only prevents use of animation at this point, and I could happily live without animation until we figure out how to solve that... Could you update the unstable 2.0.0 now on npm, so we can start testing it pls?

If you decide to release 2.0.0 as-is, perhaps consider striking onremove from documentation until this issue is resolved? It's kind of misleading and rather useless atm since it doesn't work animation, isn't it?

Either way, we can start beta-testing 2.0.0 in it's current form, yeah? 😃

[marc3lsk]

I "fixed" it like this: line 166: if(oldKey != null) { element.insertBefore(keyedNode[0], oldElement) }

But one test fails, so probably not very good fix :)

[mindplay-dk]

@JorgeBucaran if this doesn't get fixed before 2.0, do you think we should keep the omremove event in the documentation? It's sort of useless as-is, and if someone attempts to create some kind of work-around for the reordering issue, once this issue is fixed, it'll almost certainly be a breaking change.

Unless it's useful as-is (and I can't think of a use-case?) perhaps it's better to omit it from the 2.0 release and reintroduce it when it actually works?

[zaceno]

@mindplay-dk it could be more useful, or rather: easier to use - but It IS useful. How else do you suppose I do exit transitions in hyperapp-transitions? (which, despite its name, is compatible with picodom. I've added examples to the readme now too)

[mindplay-dk]

How else do you suppose I do exit transitions in hyperapp-transitions?

I don't understand how you do them now.

I've tried to read the code, which must contain a work-around of some sort to deal with the reordering issue? My main point was that, if this is fixed/changed at a later time, it should be versioned as major, as it'll likely break your library.

[zaceno]

@mindplay-dk

which must contain a work-around of some sort to deal with the reordering issue?

That is correct. The solution I found for doing FLIP animations (making elements slide smoothly from their old layout position to the new one), as it happens, also allows me to compensate for the layout change that comes from the reordering of to-be-removed elements.

But this is what I meant when I said it could be "easier to use". This workaround wouldn't be needed (by anyone). So I'm not saying this issue is not relevant. It certainly is!

My main point was that, if this is fixed/changed at a later time, it should be versioned as major

That's a good point too. And I tend to agree.

but...

as it'll likely break your library.

I can see why you would think that, but actually, it wouldn't. Just since my current solution involves looking at where an element is at all times, if it doesn't move, that works as well as if it does move.

[mindplay-dk]

my current solution involves looking at where an element is at all times, if it doesn't move, that works as well as if it does move

Okay, cool.

You could likely simplify that code if it stayed in place though?

I mean, personally, I would strongly prefer if the library did only what is required and expected, which is defer the removal of the element - if, for your solution, you needed/wanted the element to also move to the end of the hierarchy, that should be your responsibility, it shouldn't be dictated by the library, right?

It's the kind of side-effect that is difficult to describe as a "feature" - other libraries don't do this, and it would likely be surprising to most developers, as that's not at all what they asked for, and very likely not what they're expecting.

I think we can all agree on that much?

[zaceno]

@mindplay-dk

You could likely simplify that code if it stayed in place though?

Yes that is correct!

It's the kind of side-effect that is difficult to describe as a "feature" - other libraries don't do this, and it would likely be surprising to most developers, as that's not at all what they asked for, and very likely not what they're expecting.

I think we can all agree on that much?

Certainly. I agree it's not expected. And it's definitely not a "feature" either -- more like a side effect. I agree it would be nice if to-be-removed elements kept their position. That will take some time, if it ever does happen though.

The main problem is the unexpectedness of this behavior. We should definitely put something like this in the onremove section of the docs:

"From the time a node with onremove is removed, until the time the done callback is used, the corresponding element will not keep its old position among siblings. Instead it will be moved to the bottom of the list of remaining siblings."

... then at least it's not unexpected.

We actually agree on most things I think ;). The only thing I was disagreeing with is this statement:

Unless it's useful as-is (and I can't think of a use-case?) perhaps it's better to omit it from the 2.0 release and reintroduce it when it actually works?

... because if we remove it then no-one -- not even those willing to pull in another library for it -- can have exit transitions.

[zaceno]

@mindplay-dk btw, did you see I made a reusable stateful component out of your datepicker in https://github.com/picodom/picodom/issues/82 (Since you didn't reply there yet, I thought you might have missed it. Hence the crosspost ;) )

[mindplay-dk]

We should definitely put something like this in the onremove section of the docs

I have to disagree - even with a description, this is an unintended side-effect.

If we mention it at all, I think it should be designated honestly as a "known issue" and "PR welcome" - but then again, that's kind of what the issue-tracker is for.

Ideally we shouldn't release with a known issue, but as it's not a blocker for you (it is for me - I won't use this feature as-is) I wouldn't oppose releasing it as-is.

[zaceno]

Yeah let's agree to call it a "known issue". Wether it should be in the docs or not... dunno. I think it's a nice thing to give new users fair warning before they fall into a trap. Especially if it's a trap lots of people have fallen into before them 🙃

[mindplay-dk]

Tested this issue again with ultradom@2.0.0 and it still doesn't work 😢

https://jsfiddle.net/mindplay/5vkfqg8x/

[jorgebucaran]

@mindplay-dk Well, obviously, I didn't fix it for this release as I already mentioned before. I hope to tackle this when I rewrite the diff algo in Hyperapp.

[solenya-group]

I've run into the same issue discussed in this thread. I'm trying to start an animation when an element is removed, but the animation is asynchronous, so the DOM might get patched before the asynchronous operation completes. This will mean the patcher corrupts the DOM, as the patcher's "truth" of the world is a future DOM where removed elements have been destroyed. The fix, or potentially hack, I'm using to resolve the issue, is to first mark a DOM element as "removing" before the asynchronous remove operation is called:

element["removing"] = true

Then, when patching, these zombie DOM elements are filtered out as follows:

var active = Array.from (node.childNodes).filter(x => x["removing"] !== true) // consider perf + browser support
for (var i = 0; i < oldChildren.length; i++) {
   oldElements[i] = active[i]

The basic idea is that the patcher should act as if zombie elements don't exist. So long as there's a mapping function whereby the patcher's truth (i.e. the future world) can be translated to the current reality (the DOM that still includes the zombie elements), then we're OK. The issue will be that this mapping function is actually by definition not a function, because information is lost when something is removed. However, in many practical cases (e.g. to get our typical animations working) this might not matter. In addition, the patcher can get that lost information by inspecting the actual DOM elements, or potentially via an extension to the vdom API to express intent (much like we do by specifying keys).

I'm now trying to figure out issues with such an approach.

Suppose we represent dom nodes with letters, with uppercase letters indicating an ordinary element, and lowercase letter indicating that element is being asynchronously removed, and brackets indicating child elements. The current vdom only knows of uppercase letters, while the real dom knows of both uppercase and lowercase letters.

So a simple unproblematic removal of an item in a list would be:

start -> async remove B -> destroy b
ABC -> AbC -> AC

But here's some potential issues:

Ambiguous insertion order issue (i.e. should we insert X to the left or right of b?):

start -> async remove B -> insert X -> destroy b
ABC -> AbC -> AXbC -> AXC
ABC -> AbC -> AbXC -> AXC

Parent deletion issue (i.e. should we prematurely destroy b before its async remove complete?)

start -> async remove B -> remove Y -> destroy b
X(Y(ABC)) -> X(Y(AbC)) -> X -> X

Wondering how the other virtual DOM libraries deal with this.

Thoughts?

[jorgebucaran]

https://github.com/jorgebucaran/ultradom/releases/tag/3.0.0 🎉

[mindplay-dk]

Looks like there's an edge-case where, is if render() is called again before a previously deferred removal completes, the done() callback fails to execute.

https://jsfiddle.net/mindplay/6yev75o0/33/

In asynchronous apps, say, a real-time chat, or anything that has messages arriving with unpredictable timing, I'm afraid this will happen, and will lead to bugs.

You can change the inner timeout to 2000 in this example, to see what was the expected final DOM state after both transitions - as long as the update isn't too close to the previous one, it works, so we're close ;-)

I've been poking through the source to see if I could spot the problem, but I don't really have a solid theory at this point. Sorry I can't be of more help at this time...

[jorgebucaran]

@mindplay-dk What does preact do here anyway? 🤔

[mindplay-dk]

Per the docs, lets you specify the parent-node and optionally a child-node to replace - if no child-node is specified, it appends a new one to the container and returns the newly created node.

Again, this seems to be geared towards convenience, like a framework - I think a more library-like approach would be to set aside convenience concerns, just do the heavy lifting; if ultradom does all the hard work of creating the DOM tree, it's already very easy (and much more versatile) to place it yourself using standard DOM methods like appendChild(), insertBefore(), replaceChild(), etc.

I expect a library to do the difficult stuff - I never find it helpful or convenient when a library tries to make things that are already easy even "easier", because they always miss corner cases.

I would much prefer it if we could just go back to the much simpler API we settled on earlier - where the element argument is the target node, rather than it's parent, and is optional, and it always returns either the created/replaced or updated node.

It was simpler and more flexible, and makes it possible to built either the Preact-like or Hyperapp-like API yourself, or a mount() function as before, or probably any API you could dream up.

Alternatively, stop managing the previous state and just export patch() - I liked the new render() function at first sight, but it is once again less flexible than what we had before.

Bottom line is that the current approach blocks certain patterns - and the other approach doesn't prevent any of the patterns/usages that the new approach favorizes; those can still easily be implemented, it just happens to be your own choice. That layer is so small, it's definitely not the primary reason why you'd use ultradom in your framework.

Typically, your framework is going to have one or maybe two calls to this library - why would you abstract away the longer patch() signature to save somebody two minutes of thinking when they integrate the library? Just doesn't make sense to me.

If somebody wants those 3 lines of code in render() they can just copy/paste them from the README 😆

[jorgebucaran]

@mindplay-dk ?

We were talking about an edge-case with render, this convo has nothing to do with changes in the API. I asked what does preact do to avoid the bug you seem to have found. Do they even have the same issue? (unexpected reordering after keyed removal).

[mindplay-dk]

Sorry, I'm getting mixed-up between two different issues 🙄

Does preact present the same issue (or not) of "unexpected reordering after keyed removal"?

It doesn't support deferred removals, so... I have no idea.

I've never managed to implement animation in either React or Preact yet. I understand there's a whole big add-on library to do that, so it's probably non-trivial.

The unexpected reordering isn't really the issue anymore though, I think?

The new problem is done() sometimes fails during deferred removals.

Did you see this other, more aggressive example?

https://jsfiddle.net/mindplay/omovhf25/

It randomly adds one and removes another keyed element from a randomized set.

Look in the console - everytime it errors, an extra element gets stuck at the end of the range, forever - done() for that element has already been called, so an additional element reference gets "lost" every time it fails to remove one, and the elements start to pile up, one for every error in done().

Change the timing (in the last line of the script) from rand(..) to e.g. 1100 and you will see it never errors, and the order is always perfectly preserved. That part is solved 😄👍

[jorgebucaran]

@mindplay-dk It doesn't support deferred removals, so... I have no idea.

I think React/Preact's equivalent of ondestroy is componentWillUnmount, so are you saying there is no equivalent of onremove?

[mindplay-dk]

Yeah, for components, sure - but not for elements, as far as I know.

For elements, there's the ref-attribute, which as far as I know is the only element-level life-cycle feature - it gets called with the element after creation, and again with null after the element gets removed, hence (to my knowledge) no direct way of animating addition/removal of elements.

So if I had to port this example to P/React and get animation, I'd have to implement a component for the individual notifications - even then, I'm not completely sure how to defer removals, and tbh I'd prefer not to find out at this time.

In other words, I'm interested in animation if it's "low hanging fruit" only - if it was as easy as it promises to be in ultradom :-) ... if it's going be complicated, I can forego animation, which is what I concluded when I finally caved and decided to use Preact at work...