A possible approach to the "lost timestamp" issue

[jdtsmith]

Recap of the issue

A recap from #62: there is one type of information that is lost when vundo trims the "useless" tails of very long undo-buffer lists — timestamps. Emacs inserts timestamps into the modification record when modifying a saved (aka unmodified) buffer. These timestamp (TS) records are simple, and look like:

 (t 25616 45086 191805 680000) ; the numbers are the same format as (current-time)

Importantly, timestamps are inserted whether the modification in question is an "ordinary" modification, or an "undo/redo" modification. But vundo trims the latter to avoid the buffer-undo-list growing exponentially (which happens fast thanks to its ability to fly around a tree of undos). In doing this trimming, timestamps associated with undo/redo modifications are lost.

Impact

These lost timestamps show up in two ways:

1. vundo and regular undo/redo differ in their ability to correctly mark a buffer as unmodified on returning to that state; vundo cannot always recognize when it has returned to an unmodified buffer state because of this lossage. undo/redo never fails.
2. The new saved-state indication from #62 does not work when you undo to some older state, save it, then undo/redo away from it. The TS that is introduced from this is currently culled by vundo, no trace remaining.

Potential Solution

Here is a possible solution: for any new TS records found past the last ordinary modification, "teleport" them back to the equivalent node closest to the root with the same directionality. Said more precisely: for t representing the newly discovered node with the timestamp, pair (t-1, t) is mapped to equivalent pair (p-1, p), for the minimal p. Then we teleport the TS from t→p, overwriting any found there.

Diagram

In picture form (borrowing from @casouri's excellent blog post):

Outcome

To evaluate if a given node is saved, we check if the next state of that node or any equivalent node has a TS record. For example, in the diagram, node 1 is known to be saved, because its equivalent node 5 sees a TS in the next state up (node 6). This will fix problem 2 above.

Problem 1 is also fixed, as long as vundo selects a path that arrives via the adjacent TS node. So for example, in the above right-hand example, going from 0→1 is via 6→5, which works correctly. No path from 2→1 will set the buffer to unmodified, but the same would be true for regular undo/redo as well. Also note that the teleportation process, even if it overwrites an older TS, does not cause problems; undo already ignores older timestamps that do not match the file's modification time.

Cost

The cost is (sometimes) maintaining a bit more tail to track save-then-undo's. In the above example (pink node is current), normally you'd trim back to node 5. For the left scenario, you do that. For the right scenario, you trim only back to node 6.

[ideasman42]

Commenting as a user, although I have some experience with Emacs undo internals.

Note that one of the things I really like about vundo is it's simplicity and performance, compared with undo-tree (where I ran into very occasional - severe bugs). Showing the saved state seems more like a "nice to have" than being especially important.

If including such a feature adds complexity / performance overhead, then I'd prefer not support the feature at all or, optionally support the feature - so the extra complexity can be avoided if the feature is disabled.

[jdtsmith]

Valid points; I share that experience with undo-tree, and do love the simplicity and efficiency. There is a config option to disable save marking in #62 if you want to avoid seeing that information for some reason. That said, it should not impact performance at all (and will still be gathered).

This particular fix to a deep and subtle bug (timestamp information loss) would need some testing, but I don't expect it would have much performance impact either, since it's a one-time cost not associated with moving around. Note that, even if you do not care to see saved state, this matters for correctly marking buffers unmodified, which currently vundo cannot reliably do, because it trims away timestamps. I'm not sure if you've encountered that, but I definitely have... "didn't I just save that there?".

BTW, is there a test framework you or others have used to stress-test the undo system? It would be good to stress/performance test any changes.

[jdtsmith]

Here is a small stress test I wrote of the undo and vundo system. See #67.

[jdtsmith]

While I am thinking of it: I want to be clear that I consider the "incorrect buffer unmodified state" (impact 1) to be the far more significant issue than "getting the last-saved highlighted node right at all times" (impact 2). But the latter makes it quite clear that information loss is occurring.

Here's a recipe to see this yourself (using #62):

• Create a file with a fairly long (linear) set of changes.
• Using vundo, undo once, and save that state.
• Re-enter vundo: the saved node is highlighted as latest.
• Navigate forward and backwards a few times past this node, finally returning to it. Hit Return.
• The buffer is (often) marked as modified, despite having recently been saved.

If you had done the precise same set of modifications and undos/redos with the built-in emacs commands, the saved buffer state would have been correctly marked as unmodified on returning to it. This is the current price paid for "trimming the tail". Also note that TS lossage does not always happen, since vundo does save "some" of the undo/redo-only tail of buffer-undo-list, as needed. So sometimes the undo/redo-inserted TS is retained, other times it is lost. This of course makes the situation even more confusing. I often experience a related dissonance using vundo — "Wait, I did save there, didn't I?".

[jdtsmith]

OK, I did some more exploration of the "timestamp lossage" issue. I've understood a few new things:

1. Navigating back up the tree and saving for the first time a particular state (as in the example above) does introduce new timestamps into buffer-undo-list. But since they appear only in the "tail of undos", they are quite likely to be trimmed away. The recipe above demonstrates this clearly, and #73 includes some debug reporting of when this occurs.
2. For now our simple workaround is: if the current state is unmodified, mark it as latest saved. This is quite fragile and will not persist as you navigate away from that state.
3. The same TS is injected multiple times into buffer-undo-list as you navigate, which makes sense, since an undo mod records that it changed the same saved state (again). Many of these duplicate timestamps get trimmed away by vundo, but without apparent loss of information.
4. Some TS's are present in the buffer-undo-list, but are not (currently) being displayed by vundo. This is because the TS is not attached to the "master" index, but to one of its (later) equivalents. This would be the case if you returned to an old state, saved it, then introduced new changes. The next index after an equivalent (not the master node) records that timestamp.

More info in #73.

[ed9w2in6]

For me, vundo seem more buggy since I ran into the No possible route issue from time to time (rarely), which never happened on undo-tree. On another older computer that I have vundo actually corrupts my file, which I had to switch to use undo-tree. That being said, I have yet looked into the reason why, I remember some of the test not being able to pass.

May I ask if that implies if I increase the undo-limit and don't move by arrow keys (I almost only use arrow keys) such that less stuff are added to the undo list when navigating I will less likely face the No possible route error?

[jdtsmith]

My basic understanding is that moving a big distance in the undo tree adds significant length to the buffer-undo-list, which may, prior to vundo lopping off the unnecessary "leafy growth" at the tips of the tree, lead to list trimming from near the trunk by emacs. Then some branches of the tree (including the one which you may be on) can be severed and unreachable.

You can likely increase the various undo limits to help avoid this. But never totally solve. A smart pruning that respects the tree structure could help, but sounds pretty complicated. Another idea is to break large moves into a series of smaller ones, trimming the shrubbery at each intermediate step. Of course if emacs had used a tree structure (instead of a list that loops back on itself) that would be simpler.

[casouri]

Yes, increasing undo-limit should help. I don't think moving by arrow keys would add more stuff to undo list tho.

[jdtsmith]

a and e seem to be likely culprits. But it's pretty easy to get "no route" errors using the methods of #67/#69, especially near the trunk of a large tree.

[jdtsmith]

Current simplified thinking on this issue is in #81.

[mentalisttraceur]

@jdtsmith is this issue still an issue or did you fix it in #96 ?

[jdtsmith]

This is still a (minor) issue.