Replace Global History tree with Per-buffer History (prior model)

[jmercouris]

Global History is a very cool idea in concept. Unfortunately, I don't think that the implementation is something that we've managed to nail down yet. For this reason, I suggest we move to the prior model.

I have a couple of problems that keep occurring:

1. When I press "history-backwards" after making a new buffer I am often surprised with a URL that doesn't exist in the current set of buffers. I don't know from where this URL is coming from, but as a user it feels almost random.
2. The default.lisp history file has extremely long lines, is very complex, and is hard to reason about. I cannot really look at it and understand it as I could with prior models.
3. The concepts of 'owned' and 'disowned' branches on the history tree are complex and difficult to understand.
4. Frequently, when I press "history-backwards" the previous page fails to load correctly from cache and say "Network error, page cannot be reached", I have to manually refresh the page.

Even though the history has had quite some months to mature, we still have not ironed out all of the bugs. For example, today as I was working through #1649 with Pedro, I realized the immense difficulty in working with the API, and with testing it. Together we also verified: https://discourse.atlas.engineer/t/why-having-a-history-disowned-and-a-global-history-source/229. Perhaps it is not a bug, and owned history cannot be deleted, this is however very surprising to the user, and was not a limitation of our tree based history.

Benefits of previous history model:

1. simple to program, simple to debug, simple to test
2. lightweight/smaller history file
3. behavior that more users can understand/conceptualize
4. we know that it works

What do you guys think? I know it was a lot of work to develop global history tree, but I beleive it would be a better decision for us in the long run to go back to per-buffer trees.

@pdelfino @aartaka @Ambrevar

[Ambrevar]

1. When I press "history-backwards" after making a new buffer I am often surprised with a URL that doesn't exist in the current set of buffers. I don't know from where this URL is coming from, but as a user it feels almost random.

history-backwards has a bug, I just haven't found the time to get down to it.

This is not related to the GHT model though.

2. The default.lisp history file has extremely long lines, is very complex, and is hard to reason about. I cannot really look at it and understand it as I could with prior models.

Why do you want to look at the file itself? The prompt buffer does a much better job at presenting the history.

Even without GHT, default.lisp quickly becomes overwhelming.

3. The concepts of 'owned' and 'disowned' branches on the history tree are complex and difficult to understand.

Some things are complex but worth working on. We are making a Lisp browser after all :)

That said, we could provide more examples in the documentation. If you can point out the parts that you find confusing, I could work on it.

4. Frequently, when I press "history-backwards" the previous page fails to load correctly from cache and say "Network error, page cannot be reached", I have to manually refresh the page.

Yup, another bug I've been having ever since we are handling network requests. This is unrelated to the GHT though, this is the load-failed handler we must fix.

Even though the history has had quite some months to mature, we still have not ironed out all of the bugs. For example, today as I was working through #1649 with Pedro, I realized the immense difficulty in working with the API, and with testing it. Together we also verified: https://discourse.atlas.engineer/t/why-having-a-history-disowned-and-a-global-history-source/229). Perhaps it is not a bug, and owned history cannot be deleted, this is however very surprising to the user, and was not a limitation of our tree based history.

This we've discussed at length when developing the GHT. Long story short, not deleting owned entries was a design decision to greatly simplify the mental model.

That said, documentation can be improved and the bug (if confirmed) should be fixed (easy).

Benefits of previous history model:

1. simple to program, simple to debug, simple to test
2. lightweight/smaller history file
3. behavior that more users can understand/conceptualize
4. we know that it works

Agreed with 1-3, but 4 is untrue: the GHT works, we can experience it every day. It's not because there are still bugs to iron out that it does not work. The original htree had the broken "implicit visits" bug for ever and we never got down to fix it until recently.

In all fairness, we haven't worked at all on polishing the GHT since it got merged. We need to get down to it, that's it.

[aadcg]

I don't know from where this URL is coming from, but as a user it feels almost random.

Yes. Ultimately, a good old boring browser must be achieved before the infinitely extensible browser.

Some things are complex but worth working on.

Exactly.

We need to get down to it, that's it.

Exactly.

Happy hacking.

[Ambrevar]

For reference, the backward history bug is discussed here: https://github.com/atlas-engineer/nyxt/issues/1370

[Ambrevar]

I think I've found out the root of all evil: htree:current-owner-id.

This makes the GHT unnecessarily global. It breaks all the time because when a buffer is loaded and the user switches buffer around the same time, the value of current-owner-id juggles and the history entries are updated for the wrong owner!

It's obvious in hindsight that current-owner-id is a recipe for disaster.

Solution: Just remove it and systematically pass the desired owner ID from the call site.

@aartaka Any idea why we went with this current-owner-id in the first place? It seems to be that it was so that we could just chain calls more easily, e.g.:

(htree:forward (htree:forward history))

instead of

(multiple-value-call 'htree:forward (htree:forward history owner))

(Assuming `forward' would return the owner as a second value, which is not the case at the moment.)

Any other reason?

If not, I'll remove current-owner-id from htree. This will break the API, but keeping this thorn in our knees any longer is certainly a bad idea.

Thoughts?

[aadcg]

Pierre Neidhardt @.***> writes:

This makes the GHT unnecessarily global. It breaks all the time because when a buffer is loaded and the user switches buffer around the same time, the value of current-owner-id juggles and the history entries are updated for the wrong owner!

I've said this before, but it's never enough to stress. You're a genius.

[aartaka]

@aartaka Any idea why we went with this current-owner-id in the first place?

It was mostly a historical accident inherited from the previous implementation, I suppose. The initial implementation was juggling the current ID even harder than the current one does :)

No objections to removing it -- fells like a healthy move!

[Ambrevar]

I've said this before, but it's never enough to stress. You're a genius.

I don't believe in the relevance of geniusness, but I'm happy that you like my proposal :)

[Ambrevar]

See #1692 for an implementation which should, at last, make the GHT far less frustrating!

It fixes 1.

It does not fix 4. which is unrelated to the GHT and I believe it happens when cached history pages load too rapidly, or when we press multiple history-backwards too rapidly, or a combination of both.

[Kabouik]

I can confirm that 4 also happens on single history-backwards, I experience it all the time with just one H in vi bindings. But I don't doubt multiple H can only make things worse!

[Edit] *Snip, my misunderstanding.*

[whompyjaw]

I currently experience issue #4 as OP stated. And a per-buffer history seems fine. I am not sure I see the use case of a GHT. Please feel free to educate me. :)

I haven't contributed, but I am a big fan of Nyxt's idea. So I want it to succeed very much. So, maybe I can provide my "user" feedback. It would be more (efficiently) helpful if you get rid of the "map" analogy on the GHT page and just put the paragraph at the very bottom--which at least kind of explaind what GHT is versus a per-buffer history.

[mariari]

See #1692 for an implementation which should, at last, make the GHT far less frustrating!

It fixes 1.

It does not fix 4. which is unrelated to the GHT and I believe it happens when cached history pages load too rapidly, or when we press multiple history-backwards too rapidly, or a combination of both.

I can confirm that 4 also happens on single history-backwards, I experience it all the time with just one H in vi bindings. But I don't doubt multiple H can only make things worse!

[Edit] Snip, my misunderstanding.

4. is related to html codes being implemented incorrectly, nothing related to history. This error was present even before the global history buffer

The point in the code is

https://github.com/atlas-engineer/nyxt/blob/master/source/renderers/gtk.lisp#L985

Note that this is true for a wide variety of html codes. For example if one were to open a webm or mp4 the video will error with the same message once it's done. See this for example

https://github.com/stumpwm/stumpwm/pull/851

This page works with the video

https://user-images.githubusercontent.com/39150985/107167284-c7af8580-69b8-11eb-834b-f7293b241c90.mp4

This fails, you should see a black screen, if you highlight it you should get. Note that github will inline the mp4, so please copy the video link and visit it.

Page could not be loaded.

This is how we know it does not have to do with the history

[Ambrevar]

What we can do at the very least is document how to disable history globality by disabling owners, thus making the GHT effectively equivalent to the old model.

[aartaka]

(A side note: due to the move to the owned tree in #1692 (that's just a guess of mine, though), htree's globality is quite broken -- see #2014 for an example consequence of it.)

[Ambrevar]

Is it broken in other places?

[aartaka]

Yes. switch-buffer sometimes cannot switch -- it would make sense if it's for the same reason.

[Ambrevar]

Do you have a recipe?

[Ambrevar]

Friendly ping :)

[aartaka]

No, I guess -- it just happens occasionally...

To clarify -- it's actually not switch-buffer, it's switch-buffer-next that breaks and does not allow me to go to the next buffer.

[Ambrevar]

Ah, but that's unrelated to the GHT.

The issue is with the logic of switch-buffer-next itself which assumes that buffers are "owners" in the GHT. Same with switch-buffer-previous I suppose.

What happens is that the algorithm finds non-owning buffers and allows to switch to them, but when the current buffer is not an owning buffer, then it fails to find the subsequent buffer.

I think we had an open issue about this.

[Ambrevar]

https://github.com/atlas-engineer/nyxt/issues/2014 is fixed.

I'll fix switch-buffer-next.

[aadcg]

This is an important topic for 3.0. History, whatever model or approach we take, please make it dumb and reliable.

[Ambrevar]

Working on it... :p

[Ambrevar]

Should be much more reliable now with #2654.