nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
7.5 kB
274 lines
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2021 The Gleam contributors
3
4use crate::ast::SrcSpan;
5use lsp_types::Position;
6use std::collections::HashMap;
7
8/// A struct which contains information about line numbers of a source file,
9/// and can convert between byte offsets that are used in the compiler and
10/// line-column pairs used in LSP.
11#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, PartialEq, Eq)]
12pub struct LineNumbers {
13 /// The byte offsets of the start of each line of the source file
14 pub line_starts: Vec<u32>,
15 /// The total length of the source file
16 pub length: u32,
17 /// A mapping of byte offsets to character length information. This is used
18 /// when converting between byte indices and line-column numbers, because
19 /// LSP uses UTF-16, while Rust encodes strings as UTF-8.
20 ///
21 /// This only contains characters which are more than one byte in UTF-8,
22 /// because one byte UTF-8 characters are one UTF-16 segment also, so no
23 /// translation is needed.
24 ///
25 /// We could store the whole source file here instead, however that would
26 /// be quite wasteful. Most Gleam programs use only ASCII characters, meaning
27 /// UTF-8 offsets are the same as UTF-16 ones. With this representation, we
28 /// only need to store a few characters.
29 ///
30 /// In most programs this will be empty because they will only be using
31 /// ASCII characters.
32 pub mapping: HashMap<usize, Character>,
33}
34
35/// Information about how a character is encoded in UTF-8 and UTF-16.
36#[derive(Debug, Clone, Copy, serde::Serialize, serde::Deserialize, PartialEq, Eq)]
37pub struct Character {
38 /// The number of bytes needed to encode this in UTF-8.
39 pub length_utf8: u8,
40 /// The number of 16-bit segments needed to encode this in UTF-16.
41 pub length_utf16: u8,
42}
43
44impl LineNumbers {
45 pub fn new(src: &str) -> Self {
46 Self {
47 length: src.len() as u32,
48 line_starts: std::iter::once(0)
49 .chain(src.match_indices('\n').map(|(i, _)| i as u32 + 1))
50 .collect(),
51 mapping: Self::mapping(src),
52 }
53 }
54
55 fn mapping(src: &str) -> HashMap<usize, Character> {
56 let mut map = HashMap::new();
57
58 for (i, char) in src.char_indices() {
59 let length = char.len_utf8();
60 if length != 1 {
61 _ = map.insert(
62 i,
63 Character {
64 length_utf8: length as u8,
65 length_utf16: char.len_utf16() as u8,
66 },
67 );
68 }
69 }
70
71 map
72 }
73
74 /// Returns the 1-indexed line number of a given byte index
75 pub fn line_number(&self, byte_index: u32) -> u32 {
76 self.line_starts
77 .binary_search(&byte_index)
78 .unwrap_or_else(|next_line| next_line - 1) as u32
79 + 1
80 }
81
82 /// Returns the 1-indexed line and column number of a given byte index,
83 /// using a UTF-16 character offset.
84 pub fn line_and_column_number(&self, byte_index: u32) -> LineColumn {
85 let line = self.line_number(byte_index);
86 let line_start = self
87 .line_starts
88 .get(line as usize - 1)
89 .copied()
90 .unwrap_or_default();
91
92 let mut u8_offset = line_start;
93 let mut u16_offset = 0;
94
95 loop {
96 if u8_offset >= byte_index {
97 break;
98 }
99
100 if let Some(length) = self.mapping.get(&(u8_offset as usize)) {
101 u8_offset += length.length_utf8 as u32;
102 u16_offset += length.length_utf16 as u32;
103 } else {
104 u16_offset += 1;
105 u8_offset += 1;
106 }
107 }
108
109 LineColumn {
110 line,
111 column: u16_offset + 1,
112 }
113 }
114
115 /// Returns the byte index of the corresponding LSP line-column `Position`,
116 /// translating from a UTF-16 character index to a UTF-8 byte index.
117 pub fn byte_index(&self, position: Position) -> u32 {
118 let line_start = match self.line_starts.get(position.line as usize) {
119 Some(&line_start) => line_start,
120 None => return self.length,
121 };
122
123 let mut u8_offset = line_start;
124 let mut u16_offset = 0;
125
126 loop {
127 if u16_offset >= position.character {
128 break;
129 }
130
131 if let Some(length) = self.mapping.get(&(u8_offset as usize)) {
132 u8_offset += length.length_utf8 as u32;
133 u16_offset += length.length_utf16 as u32;
134 } else {
135 u16_offset += 1;
136 u8_offset += 1;
137 }
138 }
139
140 u8_offset
141 }
142
143 /// Checks if the given span spans an entire line (excluding the newline
144 /// character itself).
145 pub fn spans_entire_line(&self, span: &SrcSpan) -> bool {
146 self.line_starts.iter().any(|&line_start| {
147 line_start == span.start && self.line_starts.contains(&(span.end + 1))
148 })
149 }
150}
151
152#[test]
153fn byte_index() {
154 let src = r#"import gleam/io
155
156pub fn main() {
157 io.println("Hello, world!")
158}
159"#;
160 let line_numbers = LineNumbers::new(src);
161
162 assert_eq!(
163 line_numbers.byte_index(Position {
164 line: 0,
165 character: 0
166 }),
167 0
168 );
169 assert_eq!(
170 line_numbers.byte_index(Position {
171 line: 0,
172 character: 4
173 }),
174 4
175 );
176 assert_eq!(
177 line_numbers.byte_index(Position {
178 line: 100,
179 character: 0
180 }),
181 src.len() as u32
182 );
183 assert_eq!(
184 line_numbers.byte_index(Position {
185 line: 2,
186 character: 1
187 }),
188 18
189 );
190}
191
192// https://github.com/gleam-lang/gleam/issues/3628
193#[test]
194fn byte_index_with_multibyte_characters() {
195 let src = r#"fn wibble(_a, _b, _c) {
196 todo
197}
198
199pub fn main() {
200 wibble("क्षि", 10, <<"abc">>)
201}
202"#;
203 let line_numbers = LineNumbers::new(src);
204
205 assert_eq!(
206 line_numbers.byte_index(Position {
207 line: 1,
208 character: 6
209 }),
210 30
211 );
212 assert_eq!(
213 line_numbers.byte_index(Position {
214 line: 5,
215 character: 2
216 }),
217 52
218 );
219 assert_eq!(
220 line_numbers.byte_index(Position {
221 line: 5,
222 character: 17
223 }),
224 75
225 );
226 assert_eq!(
227 line_numbers.byte_index(Position {
228 line: 6,
229 character: 1
230 }),
231 91
232 );
233}
234
235// https://github.com/gleam-lang/gleam/issues/3628
236#[test]
237fn line_and_column_with_multibyte_characters() {
238 let src = r#"fn wibble(_a, _b, _c) {
239 todo
240}
241
242pub fn main() {
243 wibble("क्षि", 10, <<"abc">>)
244}
245"#;
246 let line_numbers = LineNumbers::new(src);
247
248 assert_eq!(
249 line_numbers.line_and_column_number(30),
250 LineColumn { line: 2, column: 7 }
251 );
252 assert_eq!(
253 line_numbers.line_and_column_number(52),
254 LineColumn { line: 6, column: 3 }
255 );
256 assert_eq!(
257 line_numbers.line_and_column_number(75),
258 LineColumn {
259 line: 6,
260 column: 18
261 }
262 );
263 assert_eq!(
264 line_numbers.line_and_column_number(91),
265 LineColumn { line: 7, column: 2 }
266 );
267}
268
269/// A 1-index line and column position
270#[derive(Debug, Clone, Copy, PartialEq, Eq)]
271pub struct LineColumn {
272 pub line: u32,
273 pub column: u32,
274}