search

casouri / vundo

Visualize the undo tree.
413 stars 20 forks source link

Move among all saved nodes #81

Closed jdtsmith closed 5 months ago

jdtsmith commented 6 months ago

This PR enables l + r to move left and right = earlier and later among all saved nodes, in time order. It is very useful with the new mark/diff functionality of #78: (m)ark, (l)ast, (d)iff is an especially powerful combo.

Changes:

Note that the timestamp alist is keyed by the master node of saved-then-changed nodes and records only the latest timestamp. There reason is that, for such nodes, zero or more equivalent nodes may have a timestamp in their next undo mod (zero if a TS is lost, see below).

TS Lossage

The one issue remaining is detailed in #73: the loss of timestamp data at the hands of trim-undo-list. This only occurs if you move back to an older node on the tree, save, and either add new non-undo edits (creating a new branch), or navigate away from there via other undos/redos. Often this "superfluous" undo is trimmed as soon as you move, since vundo reasons that it can easily reach that node without the more recent time-stamped undo record. Sometimes a "late TS" record like this can persist across vundo cycles, only to be trimmed later. I've added some temporary debugging so it's easy to see when such lossage occurs -- Trimming TS at <datetime>.

In practice this means that if you navigate back and save an older state, that timestamp is reasonably likely to be lost to trimming. Right now this doesn't cause a redraw, so a green circle can remain visible, but have no associated TS. Note that sometimes, depending on the sequence of undos/redos/edits, the same TS can appear after multiple equivalent nodes so losing one or more of these is non-problematic.

TS Loss Solutions

I see 3 possibilities:

  1. Store about-to-be-trimmed TS data in an auxiliary cache. We could simply add master_node -> time_stamp to some separate alist like vundo--buffer-timestamps every time we detect a new unmodified buffer, or an impending TS lossage (assuming these nodes are not already on the "real" TS list). Then, when navigating among saved nodes, consult both lists, as a backup. This won't survive a round-trip to disk with undo-fu-session or similar. And we'd need to save this state data to the buffer itself if we want it to persist between subsequent vundo sessions.
  2. As outlined in #73, simply copy that timestamp record (e.g. (t 25975 38996 365335 419000)) back into the next node after the master-eqv-mod-of the record prior to the mod whose TS is about to be lost (if it has no TS, or an older one). I.e. when trimming buffer-undo-list, for equivalent nodes 1a, 1b go from: ... new_child(1b, TS) <- new_parent(1b) ... old_child(1a) <- old_parent(1a) to: [Trimmed: ... new_child(1b, TS) <- new_parent(1b)] ... old_child(1a, TS) <- old_parent(1a)
  3. Just ignore the lossage, but show it, i.e. update draw if you detect a TS has been trimmed. Recall that lossage only happens when you revisit a state, save it anew, then modify it or navigate away from it. I.e. when you accumulate new modification TS's at the end of the undo list.

While number 2 is effectively rewriting history to claim that the modification to that state happened "back then", we are in a sense already doing this by eliminating superfluous recent undo records. In other words, vundo posits that the structure of the tree is what matters, not the particular historical sequence of edits/undos/redos that led to that structure (which grows quite convoluted with vundo movement).

Thoughts?

casouri commented 6 months ago

I was a bit worried by the amount of change this PR makes. But after I went over the codebase before holiday and familiarized myself with the codebase again, I think this level of change is ok. With all that said, let me find some chunk of time to go over the changes carefully and get back to you. Thanks for working on this! It should be quite useful.

jdtsmith commented 6 months ago

Thanks for the close look. It's drifted a bit from master so I need to reapply on top; will find some time for that soon so you can do a clean review.

In the meantime it would be good to come to a consensus on what to do about TS lossage, whether one of the 3 options I mentioned above, or some other better option that didn't occur to me! Currently nothing is being done: TS's sometimes get trimmed, green nodes go "out of date", and confusion can (occassionally) set in.

jdtsmith commented 6 months ago

I merged master and checked that things are working well. See above for the "hot spot" where buffer-undo-list trimming can lose TS's.

casouri commented 6 months ago

For timestamp lossage, I still prefer option 1. That feels safer and cleaner for me. We don't need to worry about losing it in the next emacs session. Let's keep that for another PR though, this PR is large enough by itself.

jdtsmith commented 6 months ago

OK, that sounds fine. In that case, this one is ready for a review.

jdtsmith commented 5 months ago

Any thoughts on the cleaned up PR?

casouri commented 5 months ago

Yeah I've been taking a bit too long. Consider it done in this weekend.

casouri commented 5 months ago

LGTM, once we made the final changes we can merge this.

jdtsmith commented 5 months ago

Squashed and ready for one last test of l/r if you have a moment.

casouri commented 5 months ago

Cool, let me give it a go

casouri commented 5 months ago

It seems you removed some unrelated code? Also could you write a formatted commit message? If you don't want to I can do that too, but I obviously don't understand the code as well as you do.

jdtsmith commented 5 months ago

Oy, this is messy. Because I merged master several times through the development of this branch, I had to soft-reset to squash. And in the process I lost a few more recent updates. I'll fix it and plump up the commit message (I'm not a branch/PR squasher, so my commit log is my rich history).

jdtsmith commented 5 months ago

Well, that didn't go as expected. I ended up just creating a new cleaned-up PR #96.