More intelligent undo system

[disordinary]

Currently every change in the post is placed on the undo stack, because of memory restrictions that stack is restricted to five. This means that a user can only undo the last five characters typed.

Usually multiple events of the same type group together as one object on the undo stack.

Events which effect undo and redo can broadly be grouped into the following (and there are likely more):

1. Text entry events
2. Forward deletion events
3. Backward deletion events
4. Paste events
5. Card change events
6. Selection / cursor change events
7. Undo and Redo events

Transitioning from one event type to another creates a single element on the undo stack.

So, my expectation as a user is to type a run of text that counts as one item on the undo stack. That is until I make a selection change, delete a character, or (potentially) a certain time limit passes, etc.

We can further group the above into different categories of undo and redo behavior:

• Events 1 -3 combine into a run to create one undo object. (a typed run, multiple backspaces to delete a word, multiple deletions to do the same).
• Events 4 and 5 always create a unique undo object and never go into a run but breaks the undo run of events 1 - 3.
• Event 6 never undos, but breaks the undo run of events 1 - 3.
• Event 7 obviously can undo and redo, and breaks the undo run of events 1 - 3.

---

I can think of three ways to accomplish this.

1. Add every change onto the undo stack, but keep track of the first element in that run, if the run is broken then discard every item associated with that run except for the last one, so we only keep the final state and the state before the change begun.
2. Create a separate stack for run characters (similar to how you already store the pendingSnapshot) and push only the latest version onto the proper undo stack when the run is broken or an undo requested.
3. Overwrite the last element of the undo stack with the pendingSnapshot if it's part of the same run.

Obviously the first two options would require a considerable increase in the number of states which are kept in memory.

Is there a reason why the number of five was chosen as a default?

[mixonic]

I think option three is reasonable @disordinary. But if you investigate and realize otherwise I would welcome some insight.

Five is fairly arbitrary, and it should also be configurable via undoDepth as a config option to the editor. We could come other with other metrics for the cost, such as a measurement of document complexity as a proxy for memory weight and make the cap work that way. Presume we can only store N sections for undo, and if a new snapshot has Y sections that push the number of total in the stack over N then evict the oldest snapshot.

[bantic]

Option 3 also seems reasonable to me. I don't think this would cause any issues.

Moving the codebase in the direction of having a better understanding of what logical changes are being made is a goal, in order to simplify a more-intelligent undo like you're proposing here, and to better facilitate concurrent editing.
Internally tracking "diffs" that roughly correspond to the 7 events listed above, would be a way to move toward this goal. For instance, as a user types text, a single "insertion diff" would be created and then appended to. After a timeout or a cursor movement the consolidated diff (e.g., "insert: 'abcdef'") could be pushed onto the undo stack. Storing diffs like this should greatly decrease the memory needed to implement undo, and I expect that it would help with concurrent editing as well.

[disordinary]

Yes that makes sense, it's obviously a huge job though.

It's probably best to sort out the undo in the near term and then look at a bigger re-engineering exercise later on.

Out of curiosity, do bustle or any other users of mobiledoc have any issues with the undo system? Because it could just be that I am undo happy but to me it's quite a big impediment.

Anyway, I'll start digging around in the codebase over the next couple of days and start working on it, no doubt I will have some questions which I'll ask in gitter.

Can you think of any scenarios in addition to the 7 above that will have an affect on the undo flow?

[disordinary]

Closing as PR now merged.