History as a Tree

[garrett-hopper]

Next browser provides the interesting feature of storing history as a tree, so when you move forward in history L/forward, it asks you which branch of the tree you want to follow. https://github.com/next-browser/next#history-as-a-tree

This might be an interesting optional feature of Qutebrowser.

[The-Compiler]

That's not possible with the API we get from Qt, and I doubt they're interested in changing that.

[mschilli87]

I have to admit that having vim's g+/g--functionality would be an excellent feature!

[garrett-hopper]

That's exactly what I was thinking, @mschilli87. :smile: That's a shame that it won't be doable.

[mentalisttraceur]

Requesting a re-open of this: QWebEngineHistory provides enough information to build our own tree of QWebEngineHistoryItem objects, if we can just hook into navigation actions.

Basic sketch of the idea:

1. Initially, the history tree is just the history line provided by QWebEngineHistory::items().

2. Normal "back" and "forward" navigation actions update which node of the tree is the current one, and navigate to that node.

3. When the engine takes a navigation action other than "back" or "forward", if there was at least one "forward item", we keep all those previous forward items as one branch off the current history item in the tree, and then the newly navigated-to item is then the first node of the newer current branch.

4. When the user takes a navigation action only possible through the history tree, such as switching branches, we save everything as the latest branch, and we can try passing the relevant saved history item to QWebEngineHistory::goToItem, but if that doesn't work (maybe it only works with items the engine still remembers in its own history list) we can at least extract the URL from the item and navigate to it.

5. Once you do a branch switch, there is a good chance that the engine is implemented in a way that makes its internal history no longer validly match the tree. So we'd want to make sure that when the user hits "back" or "forward" after a branch switch, we use the tree and not the in-engine history where those differ.

We can do the simple thing and maintain our whole tree by updating it as soon as every navigation event happens, but we might be able to optimize this a bit with some effort and code complexity:

1. We can lazily and partially populate the tree, since the history line that QtWebEngine already remembers is already the current branch of the history tree, and normal navigation actions which don't switch history tree branches will only ever lose forward items, not backward items, so part of the history tree (from the current item to the root, inclusive), is always being remembered by QtWebEngine. Until the first branch change, we only need to save earlier branches, and enough information to know where they connect on the current partially-implicit branch.

   Once a branch change happens, this gets trickier because unless the history items remember where they came from, and goToItem works on "orphan" history items from a back-then-navigate-elsewhere event, then the web engine's history effectively jumps branches of the history tree during a branch switch. At that point, it might be simpler to just give up on trying to keep track of relationships between the engine's history line and our history tree, but if it turns out to be worth keeping track of, we could add a few additional special attributes to each history tree node: still_part_of_engine_history: bool and {previous,next}_in_engine_history: HistoryTreeNode, so that our history tree effectively also remembers a doubly-linked list of the real history. (For example, if it turns out that goToItem crashes the whole engine if you give it an "orphan" history item, but is beneficial to call for non-orphan entries (maybe the engine recovers additional page state, or correctly tells webpages that it's a history navigation event, when you use goToItem), then we'd want that still_part_of_engine_history boolean.) (And of course for another example, as long as you know a node is still in the engine's history, you don't have to save your own copy/reference to the history item in its respective tree node, although this probably just needlessly complicates other code paths like "go to this node in the history tree".)

2. If Qt WebEngine will let us grab the forward items before losing them to a new navigation action, we don't even need to proactively save forward items just-in-case, we can just grab the forward items right before a history-branching navigation happens, and that list of forward items is exactly everything that we need to save at exactly the moment that we need to save it.

So anyway, it's possible to build a tree with what Qt WebEngine gives us, and I imagine a lot of users would appreciate it. If I find the time I might help with the implementation (maybe first by trying to write a more generic reusable library that solves the problem of mapping a history tree over a linear history, but sometimes it's easier to just start implementing a concrete specific use-case like just what this browser needs, and then generalize it later).

[The-Compiler]

We can detect back/forward navigation via acceptNavigationRequest:

10:14:33 DEBUG    webview    browsertab:_on_navigation_request:1088 navigation request: url https://start.duckduckgo.com/, type Type.typed, is_main_frame True
10:14:35 DEBUG    webview    browsertab:_on_navigation_request:1088 navigation request: url https://duckduckgo.com/?q=ars, type Type.typed, is_main_frame True
10:14:39 DEBUG    webview    browsertab:_on_navigation_request:1088 navigation request: url https://start.duckduckgo.com/, type Type.back_forward, is_main_frame True
10:14:41 DEBUG    webview    browsertab:_on_navigation_request:1088 navigation request: url https://duckduckgo.com/?q=ars, type Type.back_forward, is_main_frame True

but I'm still doubting that this will work out in the way you describe without the need of various hacks. Reopening for now, but reserving the right to say no to an implementation if it seems too hacky.