Byte-accurate source positions in TreeSink

[OGKevin]

Relates to #48 and #492.

Cadmus is a Reader software for e-readers.

The original HTML parsing implementation was hand written, and is not spec complete and contains some minor bugs.
While working on OGKevin/cadmus#343, I decided to give html5ever a try to replace at least the parsing bit.

It turns out, that html5ever does not provide a way to accurately know a position within a document.
The reason this is needed:

• Save and restore reading positions across sessions
• Persist bookmarks and annotations
• Resolve #anchor-id URI fragment links

For all of these to work correctly across re-parses, the offset stored on each node
must be the byte position of that node's opening token in the source string. It
needs to be stable and comparable to the raw byte sizes of the EPUB spine entries.

For the rendering of dictionary HTML, html5ever covers the use case, as there is no need for position tracking,
but it can't be used for EPUB rendering.

Would it be interesting to add the ability for when parsing a document, to store byte offsets, as this
would be the most stable way to refer to a position within a document and doesn't matter
which parsing system is being used.

[nicoburns]

Do I understand right that you're trying to use the byte-offset of the node in the source as a unique identifier for a node? Would using it's "tree position" in the parsed tree instead work? i.e. [0, 2, 0] for "first-child of the 3rd child of the first-child of the root" (0-indexed).

Presumably you have parse an entire HTML document at once anyway (so that things like styles apply correctly)? So the tree produced should be deterministic.

[OGKevin]

To save myself some agony, I wanted to remain as close to the original implementation as possible. At least, that was my initial thinking.

The original implementation indeed uses byte-offset as an identifier. And the entire document is indeed parsed. Moving away from byte offset bookkeeping would be a bigger refactor and requires me to also write a migration to migrate currently saved annotations and reading positions to this new "tree position" tracking.

Since this is an EPUB, the original implementation uses the byte offset of the combined uncompressed HTML documents.
So if the spine has three HTML files of sizes 5000, 3000, and 4000 bytes:

• Spine item 0 gets start_offset = 0
• Spine item 1 gets start_offset = 5000
• Spine item 2 gets start_offset = 8000
• etc

I did not actually investigate if your proposal would work, just that migrating away from byte tracking would be a lot of refactoring that I would prefer not to do 😆. I'll have a look at your proposed solution later 🤝 .

[OGKevin]

Yea, reading the code, migrating away from byte tracking will be a huge undertaking. I also asked AI to do the same analysis to ensure I'm not misunderstanding the scope, and it came to similar conclusions. Plato, which Cadmus is a fork of, uses byte tracking for everything(bookmarks, reading progress, annotation, location jumping, page drawing, etc). And uses binary search to quickly find the right position within an EPUB.

Using the position location as you suggested, I would need to think of a whole new algo and data structure to know which HTML document in that EPUB [0,2,0] is for. Maybe [0,0,2,0] being "first child of the 3rd child of the first-child of the root of the first spine entry". I guess binary search can still be used here, but it would be a bit more complex since you're no longer dealing with a single int.

I think my life would just be significantly easier to keep the byte tracking system, especially since there is nothing technically wrong with it and it has proven to be a good solution. I just don't see the need to maintain a custom parser 🤔.

So yea, I think having byte tracking is the way to go. I am happy to look at how to implement it in html5ever, even behind a feature flag if that's needed.

[nicoburns]

Other maintainers should probably chime in, but I suspect we accept a PR for this, but that it would indeed need to be behind a feature flag (unless it turns out not to have overhead - but I see mentions of line tracking having overhead so not too hopeful about that).

One thing I am interested in is how one defines the byte offset of a node. For an element, would it be opening <? For a text node, does it include or exclude whitespace?

[OGKevin]

One thing I am interested in is how one defines the byte offset of a node. For an element, would it be opening <? For a text node, does it include or exclude whitespace?

If you have xxx<hello where x is a space, the offset of the hello node is 4.

https://github.com/OGKevin/cadmus/blob/df4cb92578cae742dd91189b48b417786909affd/crates/core/src/document/html/xml.rs#L158-L164

[OGKevin]

Some performance numbers of the current implementation, browsing some EPUBs(1-2MBs):

[jdm]

Another consideration is what is the byte offset of the parser if it executes an inline script that calls document.write and inserts new bytes into the parsing stream?

[simonwuelker]

Another consideration is what is the byte offset of the parser if it executes an inline script that calls document.write and inserts new bytes into the parsing stream?

html5ever doesn't really know about document.write, it just provides the user with opportunities to modify the input BufferQueue at the right times. So we would have to increment the byte offset for input from document.write, like we do for the line count currently.

If there is a reasonable way to provide byte-offsets for html5ever behind a feature flag then I'm not opposed to adding that functionality. We could provide each token with a SourceLocation struct instead of the current line count, and then there's likely very little additional maintenance burden.

Note however that such information should be provided by the Tokenizer, not the tree builder as implied by the title of this issue.