Merged events producing no-op event result in incorrect state after repeated undo/redo.

[johnnesky]

Description

eventUtils.filter(...) attempts to merge related events into a single change for broadcast purposes, but in doing so it modifies the underlying events which remain in the undo/redo history. Those modified events can become no-op events even if they weren't before, reporting true for isNull(). The next time filtering is performed, these now no-op events are skipped by the merging process and important data is lost, resulting in an incorrect state in the workspace after performing undo + redo + undo.

Reproduction steps

1. Open the advanced playground.
2. From the Math category, drag a new number value block into a workspace, with the default value "123".
3. Click the number to select it, and type "1", "2", "3", producing three block change events with the following data:
   • {oldValue: 123, newValue: 1},
   • {oldValue: 1, newValue: 12},
   • {oldValue: 12, newValue: 123},
4. Undo. The filtering and merging process overwrites the newValue of the first event to 123, and then the first event is run backward, using its oldValue 123 to update the field. The events now look like:
   • {oldValue: 123, newValue: 123}, (this is now a no-op!)
   • {oldValue: 1, newValue: 12},
   • {oldValue: 12, newValue: 123},
5. Redo. The first block is skipped entirely and the second block is now the basis for merging. It is merged with the third block and its newValue 123 is used to update the field.
   • {oldValue: 123, newValue: 123}, (still a no-op, ignored during filtering/merging)
   • {oldValue: 1, newValue: 123},
   • {oldValue: 12, newValue: 123},
6. Undo again. The first event is ignored entirely, so the second event's oldValue 1 is assigned to the field, resulting in an incorrect state for the field. The field did not originally have the value 1.

[maribethb]

@BeksOmega , Rachel said we got some of the merge/filter code from App Inventor. Can you check with them if they've noticed this and have a fix for it?

[ewpatton]

@maribethb @BeksOmega So I checked out 67e192e, which was the last commit in Blockly from MIT App Inventor related to event merging. At least in the playground on that version I was unable to replicate the issue following the steps above by @johnnesky. At each undo/redo step I logged the respective stacks and they appear to have the correct information, no merging occurs. From there, I verified that indeed on develop the unexpected behavior occurs. A git bisect pointed to a commit that initially made no sense to me (switching to hosting the playground via http-server). This appears to be due to some issues on my end getting blockly_uncompressed.js to update correctly even with npm run build.

Anyway, at a high level, earlier commits in the bisect that appear good have a unique groupdId per field change event, which is triggered on every keystroke. Later commits have a groupId for the entirety of the keystroke sequence. The change in semantics here seems to cause the problem, but I haven't dug into why, and our optimizations were mainly to reduce the computational complexity of merging events from O(n^2) to O(n), so the resulting semantics should be the same, just faster (we sometimes have workspaces on order 1000 or more blocks, so quadratic operation, like clean up blocks, can be millions of operations).

[maribethb]

Thanks, Evan!

I don't have time to look into this right at the moment but your message rung a bell and I found this PR #4952 which may be related. In that one, we say it's a bug that the events didn't group related edits. Haven't thought ahead further than that yet.

[ewpatton]

I did mention to Beka in a separate channel that we may need to adjust the event merging code to treat runs of events on the same field as a collapsed event if the semantics around how individual keystores are reported has changed.

In App Inventor, we've gone further in our interpretation and we don't consider individual keystrokes to be block-event worthy and don't even report them. Only once the user has hit enter do we consider this a change to the field, at which point an event is generated. This is mainly due to our auto-saving code keying off the onWorkspaceChange event, and we don't want to save a workspace while the user in the middle of editing a field and AFAIK Blockly at the time we most recently incorporated changes (circa 2017) had no way to do this.

[ewpatton]

Ok, so I looked into this a bit more and it seems like the main reason that the logic is broken is that events within the same group are:

1. not being evaluated in the same call to filter, and
2. when undo/redoing, the events are pushed onto the redo/undo stack without regard to the outcome of the filter call.

1 is problematic because the filter operation merges events and drops them if the merged result is a null operation. However, since each event fires when the keystroke occurs, but they all have the same group ID, the individual events aren't merged into an event that says the field of the block goes from 123 to 123 (which is null and is dropped by filter). So 3 events end up on the undo stack rather than 0.

2 is problematic partly due to 1 but also undo/redo seem to not make use of the semantics of filter. More specifically here the events are pushed onto the opposing stack before filter is called, so even though filter is trying to merge and delete redundant events in the undo stack (resulting in the bug reported in this thread), its efforts are for naught. I can see that this would make sense if 1 was implemented because a group of events on the undo stack really ought to not result in null changes (i.e., if every change on the undo stack is significant than filtering again should be redundant, but there is a series of events on the undo stack that indeed represent a null operation).

The simplest fix might be to modify the undo function to filter the event list before pushing the events onto the opposing stack. However, this will still have the effect that if you repeat the sequence of events above, you will have to undo twice to remove the block from the workspace (the first undo will merge the change events into a null event, which will get removed from the undo/redo stacks, and then the second undo would remove the block) but only then be able to redo once.

A harder fix would be fixing 1 since the operations within a group are happening at different times on the run loop but filter has never been updated to accommodate this.

[johnnesky]

I have a suggested fix: Use the output of the filtering/merging process to transfer events from the undo queue to the redo queue and vice versa, instead of transferring the original events. The merging behavior makes sense in the context of the output, but the fact that the unmerged events remain in the undo/redo queue alongside the modified/merged event is what causes problems.

I would also suggest testing to see if the output of filtering/merging contains any non-null events. If not, then the undo/redo behavior should be repeated, trying the next group of events, until something actually changes, otherwise it feels weird to press undo and nothing happens.