Repository navigation
Byte-accurate source positions in TreeSink #734
Description
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-idURI 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.
Activity
[-]FR: Byte-accurate source positions in TreeSink[/-][+]Byte-accurate source positions in TreeSink[/+]nicoburns commentedon Apr 2, 2026
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 commentedon Apr 2, 2026
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:
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 commentedon Apr 3, 2026
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 singleint.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 commentedon Apr 3, 2026
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 commentedon Apr 3, 2026
If you have
xxx<hellowherexis a space, the offset of the hello node is4.https://github.com/OGKevin/cadmus/blob/df4cb92578cae742dd91189b48b417786909affd/crates/core/src/document/html/xml.rs#L158-L164
OGKevin commentedon Apr 3, 2026
Some performance numbers of the current implementation, browsing some EPUBs(1-2MBs):
jdm commentedon Apr 3, 2026
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 commentedon Apr 3, 2026
html5ever doesn't really know about document.write, it just provides the user with opportunities to modify the input
BufferQueueat 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
SourceLocationstruct 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.
YT-TechDev commentedon Aug 5, 2026
Hi!
I’m working on Frontend Analysis, a browser-independent frontend analysis tool, and we have a related tokenizer-level use case.
For explicit start tags recognized by the tokenizer, we need exact UTF-8 byte ranges for:
For example, given:
we would need ranges corresponding to:
<x-Foo class="example">x-FooThe caller would use these ranges only to slice the retained source exactly. We do not intend to change normalized tokens, token recognition, error recovery,
TokenSinkResult, or existing tree-builder behavior.Would this fit within the intended scope of this issue, or would it be better to open a separate issue specifically for tokenizer-level token and tag-name spans?
We’ve done some bounded design and prototype work, but I wanted to check the preferred scope and direction before going further.
Thanks!
OGKevin commentedon Aug 22, 2026
My PR only provides the start of tokens, basically the offset since beginning of file.
I guess with this data you can implement some math to calc the length of tokens.
We have diff use cases, I'm just interested in the token's position within the file.
YT-TechDev commentedon Aug 22, 2026
Thanks for the clarification! That makes sense.
Our use case needs exact source ranges, so it’s slightly different, but the start offsets are still useful. I’ll take a closer look at how safely we can build on that on our side.