Feature idea: Stack undos/reados as potentially undoable?

[posita]

Currently the model seems to be something like:

past: [0, 1, 2]
present: 3
future: [4, 5]

If, in this state, a mutating action is dispatched, the history becomes:

past: [0, 1, 2, 3]
present: 6
future: []

This has the effect of "forking" state at the new entry point and orphaning prior state. This may be totally intended. However, other apps may want to preserve that forked state. What about enabling (perhaps as an option) something like this?

Initial state:

history: [0]
//        ^  <- present_ptr now points here
present_ptr: 0  // index into history pointing to the current state (`== 0` indicates undo exhaustion, `== redo_upper_bound_ptr` indicates redo exhaustion)
redo_upper_bound_ptr: 0  // index into history (always ≥ `present_ptr`)

After actions 1 and 2 (each appends to history, sets present_ptr to history.length - 1 and sets redo_upper_bound_ptr to present_ptr):

history: [0, 1, 2]
//              ^  <- present_ptr now points here
present_ptr: 2
redo_upper_bound_ptr: 2

Now undo (decrements present_ptr and appends entry pointed to by present_ptr):

history: [0, 1, 2, 1]
//           ^  <- present_ptr now points here
present_ptr: 1
redo_upper_bound_ptr: 2

Undo again:

history: [0, 1, 2, 1, 0]
//        ^  <- present_ptr now points here
present_ptr: 0  // now 0 (no more undos possible)
redo_upper_bound_ptr: 2

Now redo (increments present_ptr and appends entry pointed to by incremented present_ptr):

history: [0, 1, 2, 1, 0, 1]
//           ^  <- present_ptr now points here
present_ptr: 1
redo_upper_bound_ptr: 2

Now submit action 3 (appends new entry to history, and resets both present_ptr and redo_upper_bound_ptr to history.length - 1)

history: [0, 1, 2, 1, 0, 1, 3]
//                          ^  <- present_ptr now points here
present_ptr: 6  // now same as redo_upper_bound_ptr (no redos possible)
redo_upper_bound_ptr: 6

The nice part about this approach is that it the data structure can support the existing behavior with some minor logic tweaks, namely, by not appending entries while undoing/redoing and instead truncating history at present_ptr when you get a new state. Here would be that same progression with appends turned off:

history: [0]
//        ^  <- present_ptr now points here
present_ptr: 0
redo_upper_bound_ptr: 0

After actions 1 and 2:

history: [0, 1, 2]
//              ^  <- present_ptr now points here
present_ptr: 2
redo_upper_bound_ptr: 2

First undo:

history: [0, 1, 2]
//           ^  <- present_ptr now points here
present_ptr: 1
redo_upper_bound_ptr: 2

Second undo:

history: [0, 1, 2]
//        ^  <- present_ptr now points here
present_ptr: 0  // now 0 (no more undos possible)
redo_upper_bound_ptr: 2

Redo:

history: [0, 1, 2]
//           ^  <- present_ptr now points here
present_ptr: 1
redo_upper_bound_ptr: 2

After action 3 (biggest difference; truncates history at present_ptr + 1 before proceeding as above):

history: [0, 1, 3]
//              ^  <- present_ptr now points here
present_ptr: 2  // now same as redo_upper_bound_ptr (no redos possible)
redo_upper_bound_ptr: 2

[posita]

A super cool aspect of this approach is that you could expose this as a user setting that could be toggled as the user interacts with undo-able primitives. I haven't thought super deeply about this, but I don't think it comes with many edge cases.

Regarding usability for those who have to penetrate the state (e.g. in testing), one could add another property (e.g., present) that always points to the same object as history[present_ptr] (and is updated accordingly), which would help with some slice of backward compatibility. I supposed for full backward compatibility, past and future could always be maintained as history.slice(0, present_ptr) and history.slice(present_ptr, redo_upper_bound_ptr + 1), respectively?

Actually, I think you could maintain the same data structure as now, optionally appending undos/redos to a new stack that gets shoved onto past when a new mutating action comes along. Maybe something like:

Initial state:

past: []
present: 0
future: []
undos_and_redos: []

After actions 1 and 2 (appends to both undos_and_redos and past:

past: [0, 1]
present: 2
future: []
undos_and_redos: [0, 1]

Now undo (same as current implementation, but appends prior present to undos_and_redos):

past: [0]
present: 1
future: [2]
undos_and_redos: [0, 1, 2]

Undo again:

past: []
present: 0
future: [1, 2]
undos_and_redos: [0, 1, 2, 1]

Now redo (same as current implementation, but appends prior present to undos_and_redos):

past: [0]
present: 1
future: [2]
undos_and_redos: [0, 1, 2, 1, 0]

Now submit action 3 (replaces past with a copy of undos_and_redos before proceeding as normal)

past: [0, 1, 2, 1, 0, 1]
present: 3
future: []
undos_and_redos: [0, 1, 2, 1, 0, 1]

If implemented as an option, live toggling would likely mean something like keeping undos_and_redos in sync with past all the time, but I'd have to think that one through….

[nmay231]

As you mentioned, this behavior is by design. If you think about how undo-history is implemented in (pretty much) every user application, it only keeps track of one 'branch' of history, i.e. no forking. It is much easier to implement and to reason about, and this is sufficient for most use-cases (version control being a notable exception).

If you wish to look into others' experiments with multiple future branches, I would checkout redux-dag-history. I believe it implements keeping future branches as a tree of nodes instead of a 1D array, but it allows for the same features.

Thank you very much for the idea :slightly_smiling_face: but we are going to pass on this one :+1:

[posita]

Fair. To be clear, redux-dag-history is too complicated for what I was intending for this. Assuming solely an undo/redo interface (nothing more), shoving the intermediary undo/redo steps into the linear state history (without forking) could still be valuable. In other words, the user still only has ⌘Z/⇧⌘Z (or equivalent), and they still need to work. But I respect the desire to keep scope narrow.