[zathura] [PATCH] Fix zathura's bisect

[Abdó Roig-Maranges]

Hi,

As a side effect of the new and much improved jumplist, the bisect functionality
(bound to ^j ^k) broke. I attach a patch for the bisect.

During a bisection, jump history is slightly rewritten, as explained in the
commit message. The rest of the new jumplist behaviour (besides bisects with ^j
and ^k) is not modified.

Abd? Roig-Maranges

-------------- next part --------------
A non-text attachment was scrubbed...
Name: fix-bisect.patch
Type: text/x-diff
Size: 3582 bytes
Desc: fix-bisect
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130702/0a5d059f/attachment.patch>

[Marwan Tanager]

Post by Abdó Roig-Maranges
Hi,
As a side effect of the new and much improved jumplist, the bisect functionality
(bound to ^j ^k) broke. I attach a patch for the bisect.
During a bisection, jump history is slightly rewritten, as explained in the
commit message.

When I made the changes to the jumplist code, I made a deliberate decision to
not _ever_ modify the jump history except for trimming from the beginning in
case the maximum size is exceeded. I did this for the sake of _consistency_, as
well as the fact that rewriting the jump history contradicts the very purpose
of the jumplist, which is to provide the user with the ability to go back and
forth to any and _every_ position that was a result of a jump, no matter what
the action that resulted in that jump was, be it bisection, jumping to a mark,
a page number, a bookmark, or a search result.

When the user gets used to being able to jump to any previous position with
certainty that he/she _will_ eventually find that position (except if it's
very far and got dropped as a result of trimming), then any other behavior
beside that would surely be perceived as a bug, and I'm sure that someday we
will see a bug report regarding this _inconsistent_ behavior.

AFAICS, nothing is broken as far as bisection itself is concerned, and I don't
think that bisection has anything to do with the jumplist except for just
generating new jumps, just like any other action that results in a jump.

Bisection and the jumplist are just entirely unrelated, so I don't think that
it's a good idea to change the jumplist internal data structure as a side
effect of bisection, it just doesn't make sense.

I don't mean to be stubborn or something, I just want to make my point clear.


--
Marwan

[Abdó Roig-Maranges]

Hi Marwan,

I wrote the first crappy jumplist, and the bisection code. I agree that loosing
jump history is not good for the jumplist, and I am happy with your changes.

Here is a second attempt at fixing bisect.

Post by Marwan Tanager
Bisection and the jumplist are just entirely unrelated

No they are not. The state during bisection (lower and upper bound) are stored
as the last two jumps before current in the jumplist.

Post by Marwan Tanager
I don't think that it's a good idea to change the jumplist internal data
structure as a side effect of bisection, it just doesn't make sense.

In yesterday's patch I did not touch your improved jumplist. I just change two
lines in the bisection code (sc_bisect) and exposed zathura_jumplist_save (to
rewrite jumps in sc_bisect). I'm going an other route with the attached patches,
though.

Post by Marwan Tanager
AFAICS, nothing is broken as far as bisection itself is concerned

Your jumplist code is fine (I did not touch it beside from exposing
zathura_jumplist_save). What was broken was the middle case in the bisection
code (lines 859 and 886 in shortcuts.c). The problem is related to this bisect
step:

-1 ......... 0 .........-2 .....................

Here pages increase from left to right and the numbers represent jumps (0 is
current jump).

Bisecting to the right with the broken bisect (the one after your jumplist code)
would lead to

-2 ........ -1 .........-3 .....0.................

This case (and its mirror, jumping left) are the only troublesome cases.



The thing is that the bisection code uses the jumplist to keep the lower and
upper bounds of the current bisect step as the last two jumps in the jumplist. I
didn't want to add a new "bisect mode" with more state...

Also I like the idea that bisect always uses the last two jumps as there is no
need for a "bisect initialization" telling zathura the initial bounds.

There are two ways to make sure the two jumps before current are always the
current bisect bounds:

1. Slightly rewrite history as done in the first patch I sent yesterday.
2. Insert new jumps when needed, as done in the attached patches.

I agree that loosing history is bad. The attached patches do not loose jump
history, but they mess a little with jump order (inserts a jump before last from
time to time).

In the case above

-1 ......... 0 .........-2 .....................

Bisecting to the right from 0 will now lead to

-2
-3 ......... -1 ....0....-4 .......................

It just inserts the upper bound before the current jump in the jump history and
then bisects. This way, the -1 and -2 jumps after a bisect step are still the
bounds for the bisection algorithm.

About the attached patches:

girara-list-insert.patch adds insert functionality to girara lists
zathura-fix-bisect-v2.patch adds zathura_jumplist_insert + fixes bisect


Abd? Roig-Maranges.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: girara-list-insert.patch
Type: text/x-diff
Size: 1632 bytes
Desc: girara-list-insert
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130702/3d0df5ad/attachment.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: zathura-fix-bisect-v2.patch
Type: text/x-diff
Size: 6657 bytes
Desc: zathura-fix-bisect
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130702/3d0df5ad/attachment-0001.patch>

[Marwan Tanager]

On Tue, Jul 02, 2013 at 01:15:47PM +0200, Abd? Roig-Maranges wrote:

Hi Abd?,

First of all, thanks for the time you've taken for further improving things
after my comments.

Post by Abdó Roig-Maranges

Post by Marwan Tanager
Bisection and the jumplist are just entirely unrelated

No they are not. The state during bisection (lower and upper bound) are stored
as the last two jumps before current in the jumplist.

When I said that bisection and the jumplist mechanism are unrelated, I did that
in the sense that they are there for entirely different and unrelated purposes.
The fact that the bisection code can be hacked to take advantage from the info
on the jumplist is a different story.

Post by Abdó Roig-Maranges

Post by Marwan Tanager
I don't think that it's a good idea to change the jumplist internal data
structure as a side effect of bisection, it just doesn't make sense.

In yesterday's patch I did not touch your improved jumplist. I just change two
lines in the bisection code (sc_bisect) and exposed zathura_jumplist_save (to
rewrite jumps in sc_bisect). I'm going an other route with the attached patches,
though.

I know you haven't changed the jumplist code, and I wouldn't be upset if you
have. My only objection is with the perceived inconsistency that the user
would experience as a result of your change. Just because it makes life easier
for the developer, is not a good excuse for introducing behavioral
inconsistencies to the user. All the user cares about in an application like
this, is just the way things look and feel.

Post by Abdó Roig-Maranges

Post by Marwan Tanager
AFAICS, nothing is broken as far as bisection itself is concerned

Your jumplist code is fine (I did not touch it beside from exposing
zathura_jumplist_save). What was broken was the middle case in the bisection
code (lines 859 and 886 in shortcuts.c). The problem is related to this bisect
-1 ......... 0 .........-2 .....................
Here pages increase from left to right and the numbers represent jumps (0 is
current jump).
Bisecting to the right with the broken bisect (the one after your jumplist code)
would lead to
-2 ........ -1 .........-3 .....0.................
This case (and its mirror, jumping left) are the only troublesome cases.
The thing is that the bisection code uses the jumplist to keep the lower and

^^^^

Post by Abdó Roig-Maranges
upper bounds of the current bisect step as the last two jumps in the jumplist. I
didn't want to add a new "bisect mode" with more state...
Also I like the idea that bisect always uses the last two jumps as there is no
need for a "bisect initialization" telling zathura the initial bounds.

This explains it all, and this is exactly the point that I don't agree with you
on. The problem lies in that you piggyback your bisection code on top of the
jumplist code and tries to tailor it for serving bisecting which is beyond it's
scope. Think of the jumplist as just an _abstract_ mechanism that acts as a
_recorder_ for the user jumps during the session, regardless of the actions
that resulted in those jumps.

Post by Abdó Roig-Maranges
There are two ways to make sure the two jumps before current are always the
1. Slightly rewrite history as done in the first patch I sent yesterday.
2. Insert new jumps when needed, as done in the attached patches.

I would prefer it to be done in some third way that doesn't depend on changing
the jumplist contents.

Post by Abdó Roig-Maranges
I agree that loosing history is bad. The attached patches do not loose jump
history, but they mess a little with jump order (inserts a jump before last from
time to time).
In the case above
-1 ......... 0 .........-2 .....................
Bisecting to the right from 0 will now lead to
-2
-3 ......... -1 ....0....-4 .......................
It just inserts the upper bound before the current jump in the jump history and
then bisects. This way, the -1 and -2 jumps after a bisect step are still the
bounds for the bisection algorithm.

Like I said above, I think it would be better to just make things work right
without depending on the jumplist. If there is no other way, though, then I
think it would be OK to do it this way, as a last resort.

Quite frankly, Abd?, the only thing I agree with you the most in this second
patch, is that you made zathura_jumplist_save static back again. It was just
looking horrible when it was exposed :-) (doesn't make sense at all, and
appears as coming from nowhere)

BTW, I don't have a say in what's included and what's not. This is up to the
project maintainers. I was just expressing my opinion. So, don't feel like
someone is rejecting your patch; this is not mine to say.


--
Marwan

[Abdó Roig-Maranges]

Hi,

I was just expressing my opinion. So, don't feel like someone is rejecting
your patch; this is not mine to say.

No, no, that's ok. I don't care that much about jump history, but your comments
made me understand that keeping it is good. That's why I wrote the new patch.

The problem lies in that you piggyback your bisection code on top of the
jumplist code and tries to tailor it for serving bisecting which is beyond it's
scope. Think of the jumplist as just an _abstract_ mechanism that acts as a
_recorder_ for the user jumps during the session, regardless of the actions
that resulted in those jumps.

I understand your objection. I disagree. For me using jump points to drive the
bisection has a clear advantage to any alternative I can imagine. Advantage as a
user, I mean.

Let's say I'm jumping around looking for something in page 25 (I don't know it
is there, of course). I start at page 17 and jump to page 30. Then I realize I'm
passed my target. Right there I can begin bisecting from the last two
jumps without manually setting bounds, nor entering a special "bisect mode".

The way it is implemented in the second version of the patch does not loose
history. Only some extra jump points are sometimes inserted not after but before
the last jump point. The behaviour of everything else related to the jumplist
remains consistent.

I don't see this as a problem at all. I think of the bisection mechanism (the ^j
and ^k commands) as a particular kind of movements that make bisection easier,
not as anything that has state. I see the fact that they insert some jumps as a
minor inconsistency (or enhancement of the jumplist abstract model) that makes
it more usable than the alternatives I can come up with, which are:

1. either constraining me to only add jumps at the end
2. or making bisect into a stateful mechanism orthogonal to the jumplist, with
the addition "enter bisection" and "quit bisection" overheat.

Loosing jump history during bisection was an other matter, which I agreed with
and fixed.



Just to sumarize the state of affairs for the maintainer:

- the current bisect is broken and needs fixing (it does not behave as expected
in some cases).

- Forget the first patch I sent. It forgets parts of jump history. It was a
"quick fix".

- The second patch I sent makes bisect functional. It sometimes needs to insert
a jump before, not after the last jump point, but never looses history. It
has to do so to make sure that at any step in the bisection the two jumps
before current are the bounds for the bisection. I don't see this as a
problem at all. It is both, simpler from the developer standpoint, and more
usable than anything else I could come up with.

- Marwan disagrees in using the jumplist to drive the bisection, and suggests
to implement the bisection independently from the jumplist.

Unfortunately I don't have time to contribute with more code now. I just fixed
it for myself, as I use it regularly for my work.

Abd?.

[Sebastian Ramacher]

Separating the bisection code a little bit more from the jump list is
properly a code idea. I took the opportunity to rewrite it a little bit
and came up with the attached patch. What do you think of it?

* It moves some state to zathura_t: start and end denote the range that
is bisected. last_jump is used to determine if this is a new
bisection or if one is continued.
* sc_bisect now determines first if we continue or start a bisection.
If it's a new bisection, it gets the previous two jump list entries
to determine the bounds.
* Then it calculates the new position based on the current page and the
bisection range.

I have tried a few bisection sequences and probably broke some cases
that I didn't think of, so I appreciate feedback. Also, the code to
detect the start of a new bisect run is a bit hacky and could use some
improvement.

Cheers

[Marwan Tanager]

+ if (next_page == cur_page) {
+ /* nothing to do */
+ return false;
+ }
+
+ girara_debug("bisecting between %d and %d, jumping to %d", zathura->bisect.start, zathura->bisect.end, next_page);
+ zathura->bisect.last_jump = next_page;
+ zathura->bisect.start = next_start;
+ zathura->bisect.end = next_end;
+
+ page_set(zathura, next_page);
+ zathura_jumplist_add(zathura);

I think we should add another zathura_jumplist_add call here before page_set,
in order to remember the position we jumped from (just like all other cases),
and then, instead of checking the last two jumps to determine the current
bisection bounds, we check the last one and the one before the second-to-last.


--
Marwan

[Sebastian Ramacher]

Post by Marwan Tanager

+ if (next_page == cur_page) {
+ /* nothing to do */
+ return false;
+ }
+
+ girara_debug("bisecting between %d and %d, jumping to %d", zathura->bisect.start, zathura->bisect.end, next_page);
+ zathura->bisect.last_jump = next_page;
+ zathura->bisect.start = next_start;
+ zathura->bisect.end = next_end;
+
+ page_set(zathura, next_page);
+ zathura_jumplist_add(zathura);

I think we should add another zathura_jumplist_add call here before page_set,
in order to remember the position we jumped from (just like all other cases),
and then, instead of checking the last two jumps to determine the current
bisection bounds, we check the last one and the one before the second-to-last.

What does the gain us? If we're already bisecting, the last to jump
positions are not used since the bounds are already stored.

Regards

[Abdó Roig-Maranges]

Hi,

That looks quite good to me :) I attach a couple of patches changing some
things, mainly simplifying the initial range setup. In detail:

* added / fixed some comments

* Simplified initial range setup. As we don't use the jumplist for state, we
only need to look back one jump. I mean, when we start a new bisect, we do
it between current page (which may or may not be current jump) and previous
jump.

* Save jump before page_set as Marwan suggests. This is relevant for the
initial step, in the case current page != current jump.

We don't have to check jumps -1 and -3 or anything like that though. We only
need the previous jump, and only when beginning a bisect to set the initial
range. In this case the previous jump is set by the user, and not the bisect
algorithm, so we are good.

* get rid of the cb_view_hadjustment_changed. This was there to recenter the
page when zoom-center is enabled. Now, since the jumplist stores
adjustments, this should be done right after every page_set, otherwise
duplicte jumps may appear. I think it is better to call
cb_view_hadjustment_changed from page_set. I attach a separate patch doing
that.

The patches:
page-set-fix.patch: call cb_view_hadkustment_changed from page_set
bisect-on-master.diff: simplified bisect. diff on top of master
bisect-on-sebastian.diff: diff on top of Sebastian code, so it's easier to see
what I changed.

The order to apply them is first the page-set-fix and then the bisect-on-master.

Thank you both Sebastian and Marwan for taking the time to improve this!

Abd? Roig.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: page-set-fix.patch
Type: text/x-diff
Size: 1820 bytes
Desc: page_set fix
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130706/07dfe7b4/attachment-0001.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bisect-on-master.diff
Type: text/x-diff
Size: 7941 bytes
Desc: bisect on top of master
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130706/07dfe7b4/attachment-0002.diff>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bisect-on-sebastian.diff
Type: text/x-diff
Size: 4548 bytes
Desc: bisect on top of sebastian code
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130706/07dfe7b4/attachment-0003.diff>

[Sebastian Ramacher]

Thanks, applied. Let's see how this works out.

Cheers

[Marwan Tanager]

Post by Sebastian Ramacher
Thanks, applied. Let's see how this works out.

Bad news. I get a segfault once I start bisecting:

--------------------------------------------------------------------------------------------------------------
Program received signal SIGSEGV, Segmentation fault.
0x00000000004238b6 in sc_bisect ()
(gdb) backtrace
#0 0x00000000004238b6 in sc_bisect ()
#1 0x00007ffff7bc5238 in girara_callback_view_key_press_event () from /usr/lib/libgirara-gtk2.so.1
#2 0x00007ffff76ba599 in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#3 0x00007ffff6a46140 in g_closure_invoke () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#4 0x00007ffff6a57550 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#5 0x00007ffff6a5f0cb in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#6 0x00007ffff6a5f642 in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#7 0x00007ffff77d395e in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#8 0x00007ffff77e839b in gtk_window_propagate_key_event () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#9 0x00007ffff77ead3b in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#10 0x00007ffff76ba599 in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#11 0x00007ffff6a46140 in g_closure_invoke () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#12 0x00007ffff6a572d0 in ?? () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#13 0x00007ffff6a5f0cb in g_signal_emit_valist () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#14 0x00007ffff6a5f642 in g_signal_emit () from /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#15 0x00007ffff77d395e in ?? () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#16 0x00007ffff76b8a07 in gtk_propagate_event () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#17 0x00007ffff76b8c8b in gtk_main_do_event () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
#18 0x00007ffff732dd7c in ?? () from /usr/lib/x86_64-linux-gnu/libgdk-x11-2.0.so.0
#19 0x00007ffff6786ab5 in g_main_context_dispatch () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#20 0x00007ffff6786de8 in ?? () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#21 0x00007ffff67871e2 in g_main_loop_run () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#22 0x00007ffff76b7c77 in gtk_main () from /usr/lib/x86_64-linux-gnu/libgtk-x11-2.0.so.0
--------------------------------------------------------------------------------------------------------------


--
Marwan

[Moritz Lipp]

Post by Sebastian Ramacher
Thanks, applied. Let's see how this works out.

Should be fixed with 2b6fa0cfe65bbc86995eb456215031c3aca1eaf7

Best regards and thanks for your work,
Moritz
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://lists.pwmt.org/archive/zathura/attachments/20130707/699ad5be/attachment.sig>

[Marwan Tanager]

Post by Sebastian Ramacher

Post by Marwan Tanager

+ if (next_page == cur_page) {
+ /* nothing to do */
+ return false;
+ }
+
+ girara_debug("bisecting between %d and %d, jumping to %d", zathura->bisect.start, zathura->bisect.end, next_page);
+ zathura->bisect.last_jump = next_page;
+ zathura->bisect.start = next_start;
+ zathura->bisect.end = next_end;
+
+ page_set(zathura, next_page);
+ zathura_jumplist_add(zathura);

I think we should add another zathura_jumplist_add call here before page_set,
in order to remember the position we jumped from (just like all other cases),
and then, instead of checking the last two jumps to determine the current
bisection bounds, we check the last one and the one before the second-to-last.

What does the gain us? If we're already bisecting, the last to jump
positions are not used since the bounds are already stored.

We have two cases here:

- If, after a bisection step, the user changed the adjustment of the
document, calling zathura_jumplist_add before page_set will capture
this new position and add it to the jumplist before adding the new
bisection bound. This allows for going back to that position
afterwards using ^o.

- If, after a bisection step, the user proceeded directly to the next
bisection step, calling zathrua_jumplist_add before page_set will
gain us nothing, since zathura_jumplist_add will check whether the
current position is the same as the position of the last jump on the
jumplist (to avoid adding a duplicate jump), and will find that this
is actually the case, so zathura_jumplist_add in this case would
amount to a no-op.

So, this has nothing to do with bisection. It is just the way that the jumplist
is used across all other actions that results in jumps:

1. Record the current position if it's not the latest on the jumplist.
2. Jump to the target position.
3. Record the target position.


--
Marwan

[Marwan Tanager]

Post by Marwan Tanager
So, this has nothing to do with bisection. It is just the way that the jumplist
1. Record the current position if it's not the latest on the jumplist.
2. Jump to the target position.
3. Record the target position.

Well, it turns out that this is also relevant for your new bisection changes,
as Abd? says, since it automatically takes care of the initial setup.


--
Marwan