I suggest we build a UTF-8 byte offset -> UTF-16 char offset translation table:

struct TranslationTable(Vec<Translation>);

struct Translation {
    // UTF8 byte offset
    utf8_offset: u32,
    // Number to subtract from UTF8 byte offset to get UTF16 char offset
    // for offsets *after* `utf8_offset`
    utf16_difference: u32,
}

We build it by just looping through bytes of source text. We only need to add entries to the table when a non-ASCII byte is found.

Translation rule is:

1-byte UTF8 sequence
= 1st byte 0xxxxxxx (0 - 0x7F)
-> 1 x UTF16 char
UTF16 len = UTF8 len
2-byte UTF8 sequence
= 1st byte 110xxxxx (0xC0 - 0xDF), remaining bytes 10xxxxxx (0x80 - 0xBF)
-> 1 x UTF16
UTF16 len = UTF8 len - 1
3-byte UTF8 sequence
= 1st byte 1110xxxx (0xE0 - 0xEF), remaining bytes 10xxxxxx (0x80 - 0xBF)
-> 1 x UTF16
UTF16 len = UTF8 len - 2
4-byte UTF8 sequence
= 1st byte 1111xxxx (0xF0 - 0xFF), remaining bytes 10xxxxxx (0x80 - 0xBF)
-> 2 x UTF16
UTF16 len = UTF8 len - 2

So the function to build the table is really simple:

let mut utf16_difference = 0;
for (utf8_offset, &byte) in source_text.as_bytes().iter().enumerate() {
    if byte >= 0xC0 {
        let difference_for_this_byte = (byte >= 0xE0) as u32 + 1;
        utf16_difference += difference_for_this_byte;
        table.0.push(Translation { utf8_offset, utf16_difference });
    }
}

Then visit AST and adjust all Spans by looking up the first record in TranslationTable where translation.utf8_offset < utf8_offset with binary search, and utf16_offset = utf8_offset - translation.utf16_difference.

As a fast path for files which only contain ASCII bytes, we can skip the visit entirely if TranslationTable is empty.

Potential optimizations:

Search for non-ASCII bytes by checking blocks of 16 bytes in one go with SIMD (no actual SIMD code required, can get compiler to generate SIMD instructions for us https://godbolt.org/z/9fdq7YEKh).
Split TranslationTable into 2 Vecs (SoA style) so that binary search operates over a smaller memory range.
In visit, capitalize on fact that usually offset will be close after the last offset we looked up, and make a fast path for that common case, avoiding binary search, similar to how SourcemapBuilder does.

Uh oh!

ast: an extra pass for utf8 to utf16 span offsets #8629

Description

Metadata

Metadata

Assignees

Labels

Type

Fields

Projects

Milestone

Relationships

Development

Issue actions