Feature request: setting that makes `gumshoe` act like a hybrid of browser navigation and `undo-tree`

[hab25]

AFAIU, gumshoe has a linear history, and no entry gets removed unless the entry becomes dead (as defined by gumshoe--clean et al.).

This is different from how typical history navigation systems, e.g. Google Chrome's, work. In chrome, if you are in the middle of the history stack, when adding a new entry, all entries on top of the stack get popped (and lost). Folks like me may prefer this as the following concept is intuitive: your current point position is "equal" to your current place on the stack.

However, the above leads to information loss, so gumshoe could even better by keeping a history tree and allowing tree-aware navigation commands, perhaps similar to how the popular undo-tree does it, as well as this no longer maintained and released chrome extension: https://kennethfriedman.org/projects/visual-history/ (checking this out is highly recommended, the site contains an image and video that make the idea and its value very clear)

[Overdr0ne]

You are totally correct, gumshoe just uses a simple ring buffer, and just continuously overwrites older entries, so there is no popping the way I have it implemented. This aligns with the way the Emacs undo system works by default, so I think it makes sense to also use here, at least as the default.

I have used undo tree before, and I used to use Vim, where the undo tree idea originated afaik. Let me be clear, I do want that feature too. I have to be careful though to make it worth the complexity it would add to the implementation. I honestly don't think a backtracking system like that makes any kind of sense without visual aid. You add the tree ability over a stack or ring, because at some point you would want to switch branches-- but how do you refer to that other branch? You need an ad-hoc naming system, that the user needs help keeping track of. So now we need to draw a tree and name the branches there.

Another issue is, the ring buffer automatically and simply limits resource usage. With a tree, what does that look like when a tree that branches a bunch of times wraps? It's a very strange data structure... Or you just say, it doesn't wrap, and instead grows exponentially, which means you need to harvest old branches periodically or something to keep it from bogging down a users system after so much editing...

It's certainly doable, but it's tricky, and would require a lot of refactoring to do things with an actual tree.

I think another possibility here would be to keep the ring buffer, but add an additional stack-like counter that states where the user is in that history, then (optionally) sort elements by that stack counter, and draw a sort of linear tree-like path while the user is backtracking. The undo-tree documentation draws exactly what I'm talking about when comparing undo tree to the native emacs undo system (see the "undo-systems" section, it's kind of hard to describe without that visual aid). This still will result in some ugliness when wrapping, but it would be manageable I think. My feeling is that I would try this implementation before attempting an actual tree-- it seems much safer. Would something like that work for you?

[hab25]

@Overdr0ne

but how do you refer to that other branch? You need an ad-hoc naming system, that the user needs help keeping track of. So now we need to draw a tree and name the branches there.

Consider looking at https://github.com/casouri/vundo; it is small and yet provides a very good tree visualization for emacs' built-in undo facilities (so, it doesn't use any heap-located data structures of its own).

Another issue is, the ring buffer automatically and simply limits resource usage.

To me this is quite an undesirable limitation. The user should be in control of when their history gets pruned (including being able to choose "never"), no?

With a tree, what does that look like when a tree that branches a bunch of times wraps?

Assuming gumshoe keeps using a ring buffer, and assuming (because I don't know) that emacs' undo system also uses a ring buffer, perhaps looking at what vundo does can be of help here?

Or you just say, it doesn't wrap

That would be my preference.

and instead grows exponentially

I don't see how it would be exponential; perhaps you meant "unboundedly"? I believe both time and space are linear in the number of gumshoe--entrys:

• if the user is at a leaf node (i.e. a leaf gumshoe--entry), adding a new entry should mean merely extending the current branch by one node; so O(1) additional time and space.
• else, branch off the current node (which must be non-leaf) and then do as the previous case: extend the current branch by one node; so O(1) additional time and space.
  What am I missing that would make space exponential?

which means you need to harvest old branches periodically or something to keep it from bogging down a users system after so much editing...

I suggest not using a ring buffer, instead using something unbounded. Automatic freeing of resources could be configured by gumshoe-log-len or similar; defaulting to nil to have it be unbounded. My suggestion for the pruning mechanism itself: when an entry is about to be added such that gumshoe-log-len would be violated, first remove the oldest node and all of the branches it is a part of besides the current one.

BTW, though this default could eventually bog the user's system down, you can (and I recommend it) warn on every entry if the number of entries is higher than e.g.

  (defcustom gumshoe-warn-if-number-of-entries-higher-than :type '(choice (const :tag "Never warn" nil) natnum))

where the default is some natural number of your choice. (I think annoying with warnings is a much better default than causing data loss).

would require a lot of refactoring

I agree, but note that there's no rush. I say this because I've seen too many maintainers close issues where they don't have time or interest in the near future, but fail to consider their distant future and the possibility that future maintainers and contributors could have time and interest; in those cases it is useful to have the issue still be open.

Would something like that work for you?

It would not. I would only be interested in using gumshoe if it provided tree-aware (or, at least stack-aware as e.g., google chrome does) navigation commands. Without those, navigating with gumshoe in the way I want to would require too many keypresses for my liking and a visualization would not significantly alleviate that.

[hab25]

The popular nyxt browser, written in common lisp, uses a history tree https://github.com/atlas-engineer/nyxt/blob/3ae88545f6c449f6c3134e370344fdb1f2ccbcab/README.org?plain=1#L55 . Could be a great source of inspiration.

Its source uses BSD 3-Clause License.

[Overdr0ne]

Hey, I've been pretty busy, but I basically agree with your points.

• I tried vundo, and I'm convinced that this way of doing things is viable, though windowing in Emacs can be tricky. I notice with vundo, they don't really cleanly fit the buffer to the window for example, but I like the navigation model.
• You're right, both time and space are linear in the number of entries, I didn't think about that carefully.
• I like your garbage collection idea, though I could see it getting a bit ugly, because we need to search the whole tree to decide which branch is the current and which can be dropped, then subtracting that from the total-- it's also semi-random how many nodes get garbage collected. I'll have to control how often that gets triggered. I don't consider this state unusual either, I typically keep gumshoe running through days of development, so I don't want to assume infinite history.

So, I'm going to work on this feature and get back to you.

[hab25]

https://github.com/yangwen0228/jump-tree may be interesting. However, it doesn't support navigating between files (see https://github.com/yangwen0228/jump-tree/issues/2#issuecomment-544913560).