ReaderLink: Back/Forward Location stack logic

[jonnyl2]

Continuing discussions started

• Here (ping @yparitcher); and

• here (ping @Biep) .

Rebuilt the table with corrections. Current behavior:

Step	Action	Current page	Back Loc Stack	Fwd Loc Stack	Notes
0	Start	20	--	--
1	Goto page 40	40	20	--
2	Goto page 60	60	20; 40	--
3	Back to PL	40	20	60; (40)	Pages in parentheses will be skipped (same as current pg)
4	Turn page	41	20	60; 40
4A	Back to PL	20	--	60; 40; 20
4B	Fwd to NL	40	20; (40)	60
4C	Goto page 80	80	20; 41	--	Fwd location stack is cleared (why?)

The issue is that with the current implementation, the stacks can't be used to conviently switch back and forth between a (moving) reading position and a (usually also moving) endnote/reference position in the book.

Proposed changes:

Step	Action	Current page	Back Loc Stack	Fwd Loc Stack	Notes
0	Start	20	--	--
1	Goto page 40	40	20	--
2	Goto page 60	60	20; 40	--
3	Back to PL	40	20	60	Add originating location to FLS
4	Turn page	41	20	60
4A	Back to PL	20	--	60; 41	Add originating location to FLS
4B	Fwd to NL	60	20; 41	--	Add originating location to BLS
1	Goto page 40	40	20	--
4C	Goto page 80	80	20; 41	60	Don’t clear FLS
5	Fwd to NL	60	20; 41; 80	--	Add originating location to BLS

Summary of proposed changes:

• When going Back, add originating loc to FLS
• When going Fwd, add originating loc to BLS
• Don't add target locations to FLS when going Back (or to BLS when going Fwd respectively)
• Don't clear FLS on addCurrentLocationtoStack()

This will break the functionality @yparitcher described here:

Currently after step 3, if page 40 is not on the current location stack it breaks step 4a. We want page 40, not 41 to be on the stack (imagine you clicked a link and followed the paragraph to the next page and click a second link, we want the stack progression to contain the first page, where the paragraph starts)

However, I don't quite understand what the benefit of that would be? The location stack is usually used to continue reading at previous locations which the user has left to follow some link (etc.). But if they already turned the page, doesn't that generally mean that they are finished with that page and have no need to return to it? (If it happens to be a reference page or similar, they'd be better off bookmarking it anyway, as the location stack gets reset on reloading the book.)

This how the above scenario would work with my suggested changes (starting from step 0 above):

Step	Action	Current page	Back Loc Stack	Fwd Loc Stack	Notes
1	Goto page 40	40	20	--
2	Turn page	41	20	--
3	Follow link to 65	65	20; 41	--	Follow 1st link.
4	Turn page	66	20; 41	--
5	Click 2nd link to 88	88	20; 41; 66	--	Follow 2nd link
6	Back to PL	66	20; 41	88	Goes back to where the user tapped the 2nd link.
7	Back to PL	41	20	88; 66	Back to where they tapped the 1st link.

In my opinion, that would be the correct sequence of events, or am I overlooking something?

Further, the following issue reported in @Biep's comment:

Action	Current pg	Notes
Start	6
Go to Endnotes	22
Back to PL	6
Turn page	7
Fwd to NL	6	(Expected: 22, to go back to endnotes)
Fwd to NL	22
Back to PL	6	(Expected: 7, to continue reading where user has left off)

would also work according to expectations. At the moment, instead of going back to the endnotes, the reader jumps to a previous page at first, and the location of page 7 gets "lost" and can't be returned to using the Back/Forward actions at all.

I "fixed" the code in the following file for anyone who would like to test it (it's not cleaned up yet, and I also need to do some further tests. But the previously discussed scenarios have behaved according to my expectations):

readerlink.lua.txt File location: frontend/apps/reader/modules/readerlink.lua

Maybe I'm overlooking something major, but be it as it may, I'm looking forward to reading any comments.

[poire-z]

Not reading the details of your discussions and tables :) But it feels like déjà-vu :/ maybe ? https://github.com/koreader/koreader/pull/10228#discussion_r1147324830 and around

[Biep]

@jonnyl2: If I am not mistaken your proposed behaviour is precisely the behaviour I described in my pseudocode. (And I see @yparitcher thought about doing the undo/redo thing the same way I did it: with two stacks. I think it is the accepted way to implement such a data structure, not just for undo/redo, but also e.g. when writing a Turing machine implementation. No need for index bookkeeping and the like.)

One extra thing - a separate issue - could be to save my whole variable position when exiting the document, so that previous and next locations are not lost. That is great when moving to an endnote and then having to look something else up - and upon returning to the original document wanting to return to the correct location in the main text. That effectively generalises the behaviour from locations within a single document to include jumps between documents.

[jonnyl2]

The code was pretty much all there already. So I'm not taking any credit for it. I just did a few changes. I'm sure @yparitcher had good reasons for designing it that way, but I don't fully understand the rationale. I see my current changes were also suggested back then (in the discussion @poire-z pointed to).

But that is what I created this issue for -- to continue the discussion and hopefully find a solution.

[jonnyl2]

One extra thing - a separate issue - could be to save my whole variable position when exiting the document, so that previous and next locations are not lost. That is great when moving to an endnote and then having to look something else up - and upon returning to the original document wanting to return to the correct location in the main text.

@Biep I'd be quite opposed to saving the location stacks in the permanent book metadata. The purpose of the stack is to provide quick access to recent locations. A newly (re)opened book should have a blank slate in that regard. I'd rather not open a book I last read weeks ago with previous locations that I have no recollection of. (Also think about how long the stacks could get.)

However, please take a look at #13378. I created that issue mostly out of frustration with the Bk/Fwd location stack (and the crashes, which thankfully have now been fixed), but even if we resolve the issues at hand there may still be a worthwhile use case for that idea. It works like a special bookmark, but it can only be at one point in the book at any given time, and it would be persistent. (If interested, I'd suggest to continue the discussion in that issue, so we don't lose track of the Bk/Fwd logic issue in this ticket.)

[Biep]

I see your point - that the stack would also remain in "non-stacking" situations. In that case I'd like - but that sounds like a way larger request - a way to "push" and "pop" documents, a way to open another (e.g. reference) document and then pop back into the original document, still having my stack there. When truly exiting a document the stack could then be forgotten.

I think that idea at least has this for it that it is still about Fw/Bw. 😉

At the moment it is slightly possible to do this one level deep by reading the reference document in the native software, and then "popping back" to KOReader.

A special option "Exit while keeping the stack" would also be sufficient - a "normal" exit would then delete the stack. Or a setting (default is true) Delete stack upon exit, together with an (independently useful) Delete stack command that will simply set the forward and backward stacks to {}. Weirdos like me could then change the value of that setting, and do the deletion by hand.

Your #13378 would work for one-deep stacks, wich may be the majority of use cases, and as such would lighten the load. Though often enough I get into deepish "reading up" stacks, where some subject is mentioned which I realise I need to read about before continuing my (relatively) main subject. Such a mention may be a link, or send me to the table of contents and jump from there - only to have me find another term or subject to read up on about. And at times those subjects send me to other documents (either in the same series or unrelated).

[yparitcher]

I don't have time now to think this over in depth, but a few points.

I don't remember exactly why i liked the way it is currently implemented, so will not oppose on principle a PR to change implementation.

Also the reason the forward stack is cleared when going to a new link is that time (history) is linear so it only makes sense to have one forward path. (Try using the undo + redo functionality in most applications, once you make a different change you lose the redos), you can only pick one future. IE. In 4C. By clicking a link you are choosing a new forward (all links are forward) which contradicts and discards the current forward.

[Biep]

There is a good model for having a tree history instead of a linear one - in a previous millennium I have implemented one in a Scheme programming environment I wrote - but it requires a quite different way of thinking, with no distinction between past and future, but just a set of existing paths one can take, plus the option to create a new path from the node where one is. If anyone wants I could write the logic for that - it is not hard at all - but given that linear undo/redo is the norm pretty well everywhere, I am afraid it would be confusing for any newcomers (despite being quite logical and practical once one gets the hang of it - and of course the linear history being just a degenerated special case of it).

Edit: But then, it could be written it such that moving linearly be the default, and taking other paths would require extra work. That way most user might not even be aware of the fact that the history is richer than a single time line.

[jonnyl2]

Also the reason the forward stack is cleared when going to a new link is that time (history) is linear so it only makes sense to have one forward path.

@yparitcher That makes sense. I was thinking that it could be beneficial to quickly skip a few pages using Page browser or SkimTo, or jump to the next chapter, without losing (e.g.,) the position in the endnotes as Forward location. But storing forward locations from separate paths would indeed only create a mess. So I put self:onClearForwardLocationStack() back in:

readerlink.lua.txt

@Biep: Your "tree history" idea sounds interesting. I don't think it will have much of a chance but I'd like to know more about it. How would that even work? Would you then need separate gestures to follow different branches along the tree? And how would KOReader know which pages you browse to belong to which branch? Not really following so far, but I'm intrigued :)

[Biep]

Yes, the UI side would be a challenge - I was speaking about the conceptual side. And no, I am not proposing it be implemented for this use case.

In the general case: There would be a tree, with a current node (the data of which would adapt with each "go to next/previous page"). Each node has a list of pointers to other nodes, of which the first would point to the node one came from with the last jump, the second the one one one came from the last time one visited this node, and so on. So one would enter a number to choose the path. (This can of course be presented differently, e.g. visually, or as a list of node descriptions - in our case maybe page numbers.) One can also move to a new place, creating a fresh node pointing back to the current one, which gets that fresh node as its new first element, shifting the others (like a stack push), the fresh node then becoming the new current node. This can be embellished, most obviously by commands to prune certain subtrees that are deemed no longer interesting.

In our case: A general notion of going forward or backward should be retained (and associated with each element of the pointer list), and the the first two nodes on the list of each node should represent the ones from the last backward and forward jump, respectively. That way one can have commands (and gestures) for go forward and go backward that are tree-agnostic, and only see a doubly-linked list.

Does that make sense?

In the more general undo/redo context, each link also had a function that was the inverse of the action executed, so as to change the machine state back to the situation associated with the target node. So if a new node were created by, say, deleting some text, a corresponding text insertion function would be associated with the link back - and the deletion itself with the link forward. If the time taken for the action was large relative to the resulting change, often more efficient functions could be associated. E,g, a huge search might turn up some bit of data (a record, file, whatever) - but the associated function would simply keep a pointer to the data found, and place that copy in the search result register, so that a redo would be speedy. Or a full computation checking the correctness of a large program would be replaced by a trivial function returning true or false. Conversely, a fraction-of-a-second delete of a 1TB file would create a huge inverse function - hence the embellishment to prune subtrees.