EPUB page numbers freeze when the page-list nav is not in spine/reading order

[albertmichaelj]

Full disclosure, I diagnosed the bug and wrote the below issue with the help of Claude. I do not know this code base well enough to propose a fix on my own, and I cannot say with any certainty that the below fix is not going to have some unintended consequences, which is why I am not opening a pull request (just an issue with a potential fix already outlined in case it is helpful). The problem is hopefully clear, and this is something that I run into constantly because I have re-ordered all of my page lists to correspond to the print order (though I have not changed the spine). The reason for this is that in most readers (including Apple Books and Readest), the UI that shows "Page # of Total Page #" is broken if you do not reorder the page list. Specifically, in the very common case in which some frontmatter is moved to the backmatter (often copyright), you end up with something that looks like "Page 45 of iv". If you re-order the page list (which is both conformant to the ePUB spec, see below, and something that occurs on a reasonably large number of commercially available ebooks) to match the logical page order instead of ePUB spine order, other readers correctly display the total number of pages (as the final symbol in the page list). However, crengine does not handle page lists that are not ordered in ePUB spine order as described below.

Thank you for your time in reviewing this issue, and please let me know how I can make things clearer or provide testing/feedback in any useful way!

Summary

crengine's source page numbers ("reference pages") are computed from the EPUB page-list
under the assumption that the list is already in reading order. When a (spec-valid) page
list is not in spine order, the displayed page number freezes on the last in-order label
and does not advance until the reading position physically reaches the out-of-order target.

The engine actually resolves each page target to its true position and then discards that
information by forcing the values to be monotonically non-decreasing in list order. The
current page is order-independent by definition, so this is a logic error, not a limitation
of the input.

Environment

• crengine: master
• Reproduced in KOReader (reference pages / "page N of M" footer). Apple Books, Readest, and other
  reading systems handle the same files correctly because they resolve target positions
  rather than trusting list order.

Steps to reproduce

Two minimal EPUBs are attached (both have had the extension changed to .zip due to file upload limitations). Both have an identical spine and content and differ only in the order of the <nav epub:type="page-list"> entries:

• Spine (reading order): title(i) → ch1(1) → ch2(2) → ch3(3) → copyright(ii)
  i.e. a front-matter page (ii, on the copyright page) that the conversion placed at the
  back of the spine — a very common epub layout.
• A_logical_order_FREEZES.epub — page list in logical/print order: i, ii, 1, 2, 3
• B_reading_order_OK.epub — page list in reading/spine order: i, 1, 2, 3, ii (control)

Open each and page through it, watching the source page number.

B_reading_order_OK.zip
A_logical_order_FREEZES.zip

Expected

The current page label is the label of the nearest page-break at or before the reading
position. This is purely a function of each target's resolved position, so both files must
behave identically:

page 0 → i    page 1 → 1    page 2 → 2    page 3 → 3    page 4 → ii

B behaves exactly like this.

Actual (file A)

 label     target   true_page   used_page
     i      title           0           0
    ii  copyright           4           4
     1        ch1           1           4   <-- real position overwritten
     2        ch2           2           4   <-- real position overwritten
     3        ch3           3           4   <-- real position overwritten

rendered page 0 → 'i'
rendered page 1 → 'i'   (frozen; expected 1)
rendered page 2 → 'i'   (frozen; expected 2)
rendered page 3 → 'i'   (frozen; expected 3)
rendered page 4 → 'ii'

The page number sticks on the last correctly-placed label (i) through the entire body and
only "unfreezes" when the reading position reaches the out-of-order entry near the end.

Root cause

The page map is populated in XML/list order in crengine/src/epubfmt.cpp
(ReadEpubNavPageMap, and likewise ReadEpubNcxPageList / ReadEpubAdobePageMap): each
<li> is resolved to an ldomXPointer and appended via LVPageMap::addPage(), so
LVPageMap::_children is in list order. Each item keeps its resolved ldomXPointer, and
LVPageMapItem::getDocY() returns the item's true document Y from that pointer — so the
correct position is available.

The problem is in LVDocView::updatePageMapInfo() in crengine/src/lvdocview.cpp:

// Ensure page and doc_y never go backward
int prev_page = 0;
int prev_doc_y = 0;
for (int i = 0; i < pagemap->getChildCount(); i++) {
    LVPageMapItem * item = pagemap->getChild(i);
    if (!item->getXPointer().isNull()) {
        int doc_y = item->getDocY(true);          // true position (correct!)
        int page  = /* FindNearestPage(doc_y) ... */;
        item->_page = page;
        if ( item->_page < prev_page )            // <-- clamp in LIST order
            item->_page = prev_page;
        else
            prev_page = item->_page;
        if ( item->_doc_y < prev_doc_y )
            item->_doc_y = prev_doc_y;            // <-- same for doc_y
        else
            prev_doc_y = item->_doc_y;
    }
    else { item->_page = prev_page; item->_doc_y = prev_doc_y; }
}

The loop walks the items in list order and forces _page/_doc_y to never decrease. For any
entry whose true position is earlier than its list predecessor, the real value is replaced by
the predecessor's. One out-of-order entry (a front-matter page whose file sits at the back)
raises prev_page/prev_doc_y to a back-of-book value, and every later entry is clamped up
to it — which is the freeze.

Since epubcheck removed the reading-order requirement for the page list (fixes
epubcheck#1237) and the EPUB Accessibility guidance explicitly says a page list whose
front/back matter was shuffled during conversion should point to the equivalent location and
should not be renumbered, a page-list that is not in spine order is conformant input
that the engine currently mishandles.

Proposed fix

The monotonic invariant that downstream code relies on should be established from the
resolved positions, not from list order. Concretely, in updatePageMapInfo():

1. First pass: assign every item its true doc_y and _page from its XPointer, with no
   clamping.
2. Order the page map by resolved doc_y (a stable sort, so unresolved / equal-position
   entries keep their relative slot), then derive _page from the ordered positions.

Representative shape:

// pass 1: resolve true positions, no clamping
for (int i = 0; i < pagemap->getChildCount(); i++) {
    LVPageMapItem * item = pagemap->getChild(i);
    int doc_y = item->getXPointer().isNull() ? -1 : item->getDocY(true);
    item->setDocY(doc_y);
    int page = -1;
    if (doc_y >= 0) {
        page = m_pages.FindNearestPage(doc_y, 0);
        page = (page < 0 || page >= getPageCount(true)) ? -1 : getExternalPageNumber(page);
    }
    item->setPage(page);
}
// pass 2: order by resolved position instead of clamping in list order
pagemap->sortByDocY();   // new LVPageMap helper; stable sort on _children by _doc_y
// (optional) forward-fill only genuinely-unresolved (doc_y < 0) items from neighbours

LVPageMap::_children is private, so this needs a small sort helper on LVPageMap (it is a
friend of ldomDocument, and LVPtrVector already supports sorting with a comparator). A
comparator on _doc_y is enough.

Note this reorders the page-map, which is the "go to page" list shown to the user. For a
spec-conformant reading-order list this is a no-op; for a shuffled list it makes the jump
list follow reading order, which is the desired behaviour (jumping to a page lands at the
right spot).

Alternative, if reordering _children is undesirable: keep list order for the menu, drop the
clamp, and make the current-page lookup a position-based floor search (largest resolved
doc_y ≤ current position) instead of relying on the monotonic _page. Sorting is the
smaller change and fixes both the current-page display and page jumping at once.

Patch

A patch implementing the sorting approach is attached (crengine-pagelist-order-fix.patch).
It is crengine-only (no koreader-base/frontend change needed — the frontend keeps reading
getChild(i)/getPage()/getLabel(), now in reading order):

• LVDocView::updatePageMapInfo() (lvdocview.cpp): split into resolve → sortByDocY() →
  forward-fill, so positions are established before the "never go backward" step, which then
  only smooths equal/rounded positions instead of masking real reorderings.
• LVPageMap::sortByDocY() + compareByDocY() (lvtinydom.h / lvtinydom.cpp): stable sort
  of _children by resolved _doc_y, tie-broken on original index to preserve page-list
  order for entries that share a position.

It applies cleanly against current master (git apply --check passes). One note: because
the page map is serialized in _children order, already-cached books get corrected on the
next re-render (when updatePageMapInfo is re-run on page-info invalidation), not
necessarily on first reopen from cache.

crengine-pagelist-order-fix.patch

[poire-z]

Haven't yet fully read the above.
And I notice you made a frontend fix (user-patch).

We do some (possibly similar ?) fix for the ToC in frontend:
https://github.com/koreader/koreader/blob/be93502dab7cf793f8cd7685bafda41e33c6d363/frontend/apps/reader/modules/readertoc.lua#L175-L178
It was done in frontend because it's easier :) and because the requirements of the ToC being ordered is a frontend one.

No feeling yet if that pagemap ordering fix belongs in crengine or in frontend.
But you, now knowing we do that for ToC in frontend, and having done the fix both in frontend and in crengine, do you still think it belongs in crengine ?
(I'm not opposed to it - haven't read the code yet, just asking before I really read it in the coming days, so I also get a feeling.)

[albertmichaelj]

@poire-z Thanks for taking the time to respond! First, I really appreciate your work on this project, and I ultimately defer to your expertise as to whether or not it's worth trying to fix crengine directly. However, I do think that the "best" thing (in terms of outcome, not in terms of effort) is to fix crengine.

One clarifying point I want to make is that I did create a user patch (you can find the user patch in a git repo I have of KOReader user patches I've created, with the help of AI, here), but the patch I include in the issue above is not a user patch. It is a potential patch for crengine that I provided as a possible example of a fix. Though, as stated above, I do not understand the code well enough to be confident that it is both correct and will not cause unintended side effects.

My user patch is a monkey patch though. It needs to touch multiple parts of the code, and even with that, it does not actually fix everything. Specifically, with or without my user patch, the page numbers in the margin are entirely broken when the page list is not in spine order. With the existing behavior of crengine, the page numbers in the margin end up broken (with all of the page numbers being placed in the margin at the position where spine order is reasserted, in the example file A I provide in the issue, the pages in the margin would all appear on page "ii" all jumbled together). I am s

I think the cleanest approach, and to the best I can understand not one that requires a lot of modifications to the existing code, would be to fix crengine directly. I also think this is more consistent with existing epub standards. However, I ultimately am happy to defer to your expertise as to whether or not it is a big enough issue to warrant a fix, though I do think that the fix is pretty minor as far as how much of the code it changes.

Happy to help in whatever (limited!) way I can!

[tachibana-shin]

I have a suggestion for this issue: tachibana-shin@5dd88b3 Although I have some reservations about adding a for loop that runs from 0 to nb, I believe the impact on performance is negligible. I’m also fairly certain that any unintended behavior is unlikely to occur

[poire-z]

Haven't had time to review the OP proposal yet.
But I prefer it to your suggestion and its usage of libstdc++ algorith.h (I guess) and its std::sort() : crengine has its own "library"/implementations of many things usually found in libstdc++, and we don't really need or use any std:: stuff (only for interactions with thirdparties libraries like std::unique_ptr), and using it would bloat libcrengine.so and taint its original spirit.

[tachibana-shin]

Haven't had time to review the OP proposal yet. But I prefer it to your suggestion and its usage of libstdc++ algorith.h (I guess) and its std::sort() : crengine has its own "library"/implementations of many things usually found in libstdc++, and we don't really need or use any std:: stuff (only for interactions with thirdparties libraries like std::unique_ptr), and using it would bloat libcrengine.so and taint its original spirit.

I've made the update. I found the sort function in stdlib.h, but I don't think I should use it—it seems to be an implementation of quicksort. I'm certain that in most cases it will run slower than insertion sort because the number of pages is very small. In my experience, insertion sort only starts to slow down after about 500

[poire-z]

I have a suggestion for this issue

The OP obviously had a suggestion ready and shared some bits of it, and was just asking for our blessing before making a proper PR.
What about your suggestion ? You had that already done before reading this issue ? Or you hacked around once you read it, not realizing OP have some code available ?
Or did you read it and your suggestion feels to you like a better alternative ? If yes, please say why it is. If no, please look at the original proposal and how it differs from yours, so you can answer if/why it is better :)
(I have not yet read it, and I don't want to have to decide which of the 2 is better).

[tachibana-shin]

I have a suggestion for this issue

The OP obviously had a suggestion ready and shared some bits of it, and was just asking for our blessing before making a proper PR. What about your suggestion ? You had that already done before reading this issue ? Or you hacked around once you read it, not realizing OP have some code available ? Or did you read it and your suggestion feels to you like a better alternative ? If yes, please say why it is. If no, please look at the original proposal and how it differs from yours, so you can answer if/why it is better :) (I have not yet read it, and I don't want to have to decide which of the 2 is better).

To clarify, I have no intention of posting a PR for this. This is part of updating crengine to enable it to support my CSS 3 standard (I won't be posting a PR for this either). I'm leaving this here as a reference code (I have code to update all the properties lol).

[tachibana-shin]

You might think I'm trying to take credit. That's a dangerous thought; if I intended to post a PR, I would have done so immediately and said nothing. I'm leaving this here as a reference code so the OP can look at it if needed (and other things about CSS3 support if he needs it) - a spirit of sharing, not competition.

[poire-z]

You might think I'm trying to take credit. That's a dangerous thought

I'm not thinking that.
It's good someone is using AI to find all these little bugs to eventually have them fixed (but it is exhausting having to review so many - and the AI write a lot).
As for this topic here, and some other writing of yours in your other PRs, it's a bit hard to figure you where you come from and where you're going :) May be English is not your native language (not mine either), but you have chains of thoughs (like "This is part of updating crengine to enable it to support my CSS 3 standard": what this has to do with CSS3 enhancements ?!) and ignore some questions (like mine above: what's better in your suggestion vs OP ? here's a suggestion, figure how it's better yourself ? :/), that doesn't make things easier.
Nothing personal, just letting you know.

[tachibana-shin]

Perhaps my understanding of "suggest" and yours are completely different. In my opinion, a suggestion should be considered a reference, not for you to choose one over the other, but to see how others implement it. You're right, English isn't my native language, so someone helped me translate them. Regarding CSS3, to be more precise, I'm trying to support the latest epub standards and almost every border case to deal with the strange files from my favorite publisher

[tachibana-shin]

You're talking about using AI to find errors? I guess that's not a good idea. I've used it before, and about 99% of the time it was a false positive(Perhaps the model I'm using, ChatGLM 5.4, is too weak?), so I stopped using it and only use it for diff summarization.

[tachibana-shin]

You don't like the small pr? No problem, just say you don't like them and I'll remove them - you know whether that function is actually used or not, that's much more useful. I only read the lines of code and see if it might cause an error in a very short context (not the whole Koreader to see if it might cause an error). All the pr are just guesswork, it only causes local errors within a radius that I can observe

[tachibana-shin]

I'm extremely relaxed about this issue; too many (PRs) will frustrate the maintainer – I understand that. I've closed hundreds of PRs in a row and have also been asked to close hundreds of PRs (so language doesn't get in our way: I have absolutely no problem with this, or perhaps you're concerned about too many PRs to this repo being closed?)

[poire-z]

Having read both versions, I think I prefer @tachibana-shin 's take: because of its needs_sort, which avoids the sort when not needed, and because AI tells me that for mostly sorted lists, his sortByDocY() is more efficient (can't really dig into such algorithms, so trusting you both).
AI tells me that for @tachibana-shin 's version, and unlike @albertmichaelj , it does not update _index afterward:

The first implementation’s extra pass to reset _index adds linear overhead, but that is usually negligible compared with sorting cost. The second implementation keeps the sort stable by comparing _index, but because it doesn’t renumber _index, later code may see stale indices unless that field is intentionally meant to remain as the original order marker.

So, maybe this should be fixed ?

Anyway, fine with having that done in crengine. Let's keep @albertmichaelj first big comment about the context.
I let you both decide who makes a PR :)