1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// UTF-8 byte offset -> UTF-16 code-unit offset translation (compatibility
// contract §5.5, the port design notes).
//
// web-tree-sitter (WASM, what the Node implementation loads) parses a JS string
// and reports spans in UTF-16 code units. Native tree-sitter parses a UTF-8 byte
// buffer and reports spans in UTF-8 bytes. Rows always agree between the two and
// CRLF is harmless either way -- only byte offsets and byte-relative columns
// diverge, and only across multi-byte characters:
// - a 2-byte UTF-8 char is 1 UTF-16 unit -> divergence -1
// - a 3-byte UTF-8 char (incl. an unstripped BOM) is 1 -> divergence -2
// - a 4-byte UTF-8 char (astral, UTF-16 surrogate pair) -> divergence -2
/// Maps UTF-8 byte offsets in one source file to UTF-16 code-unit offsets.
pub struct OffsetTable {
/// (byte offset immediately after a multi-byte char, cumulative
/// UTF-8-bytes-minus-UTF-16-units divergence up to and including that
/// char). Sorted ascending by construction (`char_indices` is
/// monotonic); empty for ASCII-only source, where byte offset always
/// equals UTF-16 offset.
breakpoints: Vec<(usize, i64)>,
}
impl OffsetTable {
/// Builds a lookup table for the byte boundaries in `src`.
pub fn build(src: &str) -> Self {
let mut breakpoints = Vec::new();
let mut divergence: i64 = 0;
for (byte_start, ch) in src.char_indices() {
let utf8_len = ch.len_utf8() as i64;
let utf16_len = ch.len_utf16() as i64;
if utf8_len != utf16_len {
divergence += utf8_len - utf16_len;
breakpoints.push((byte_start + ch.len_utf8(), divergence));
}
}
OffsetTable { breakpoints }
}
/// Cumulative divergence in effect at `byte_offset` (i.e. contributed by
/// every multi-byte char that ends at or before it).
fn divergence_at(&self, byte_offset: usize) -> i64 {
match self
.breakpoints
.binary_search_by(|(pos, _)| pos.cmp(&byte_offset))
{
Ok(idx) => self.breakpoints[idx].1,
Err(0) => 0,
Err(idx) => self.breakpoints[idx - 1].1,
}
}
/// Translate one UTF-8 byte offset (must land on a char boundary, which
/// every tree-sitter node boundary does for valid UTF-8 source) to its
/// UTF-16 code-unit offset from the start of the file.
pub fn byte_to_utf16(&self, byte_offset: usize) -> usize {
(byte_offset as i64 - self.divergence_at(byte_offset)) as usize
}
/// Translate a tree-sitter point -- `byte_offset` from the start of the
/// file, `column_bytes` from the start of its row -- into
/// (utf16 offset from file start, utf16 column from row start). Rows
/// themselves are never translated; §5.5 rows always agree.
pub fn translate_point(&self, byte_offset: usize, column_bytes: usize) -> (usize, usize) {
let line_start = byte_offset - column_bytes;
let offset_u16 = self.byte_to_utf16(byte_offset);
let line_start_u16 = self.byte_to_utf16(line_start);
(offset_u16, offset_u16 - line_start_u16)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn ascii_has_no_divergence() {
let src = "class Widget {}\n";
let table = OffsetTable::build(src);
for byte in 0..=src.len() {
assert_eq!(table.byte_to_utf16(byte), byte);
}
}
#[test]
fn bom_diverges_by_two() {
// U+FEFF (unstripped BOM): 3-byte UTF-8, 1 UTF-16 unit -> -2.
let src = "\u{FEFF}class Widget {}";
let table = OffsetTable::build(src);
assert_eq!(table.byte_to_utf16(0), 0);
assert_eq!(table.byte_to_utf16(3), 1); // right after the BOM
assert_eq!(table.byte_to_utf16(3 + 5), 1 + 5); // "class" follows it
}
#[test]
fn accented_char_diverges_by_one() {
// 'e' with acute accent (U+00E9): 2-byte UTF-8, 1 UTF-16 unit -> -1.
let src = "// caf\u{E9}\n";
let table = OffsetTable::build(src);
let accent_byte_start = 6; // "// caf" = 6 ASCII bytes before it
assert_eq!(table.byte_to_utf16(accent_byte_start), 6);
assert_eq!(table.byte_to_utf16(accent_byte_start + 2), 7);
}
#[test]
fn cjk_char_diverges_by_two() {
// U+4E2D ('中'): 3-byte UTF-8, 1 UTF-16 unit -> -2.
let src = "// \u{4E2D}\n";
let table = OffsetTable::build(src);
assert_eq!(table.byte_to_utf16(3), 3); // before the CJK char
assert_eq!(table.byte_to_utf16(3 + 3), 4);
}
#[test]
fn astral_emoji_diverges_by_two_via_surrogate_pair() {
// U+1F600 (emoji): 4-byte UTF-8, 2 UTF-16 units (surrogate pair) -> -2.
let src = "// \u{1F600}\n";
let table = OffsetTable::build(src);
assert_eq!(table.byte_to_utf16(3), 3);
assert_eq!(table.byte_to_utf16(3 + 4), 3 + 2);
}
#[test]
fn multiple_multibyte_chars_accumulate() {
let src = "\u{00E9}\u{00E9}"; // two 2-byte chars back to back
let table = OffsetTable::build(src);
assert_eq!(table.byte_to_utf16(0), 0);
assert_eq!(table.byte_to_utf16(2), 1);
assert_eq!(table.byte_to_utf16(4), 2);
}
#[test]
fn column_ignores_divergence_from_earlier_lines() {
// Line 1 has two 2-byte accented chars (-1 each, -2 total by its
// end). Line 2 is pure ASCII: its column must not inherit line 1's
// divergence, only the file-global byte offset should.
let src = "// \u{00E9}\u{00E9}\nclass Widget {}\n";
let table = OffsetTable::build(src);
let widget_byte = src.find("Widget").unwrap();
let line_start_byte = src.find("class").unwrap();
let column_bytes = widget_byte - line_start_byte;
assert_eq!(column_bytes, 6);
let (offset_u16, column_u16) = table.translate_point(widget_byte, column_bytes);
assert_eq!(
column_u16, 6,
"line 2 is ASCII; column must equal raw byte column"
);
assert_eq!(
offset_u16,
widget_byte - 2,
"global offset reflects line 1's -2 divergence"
);
}
}