diff options
author | Kevin DeLorey <[email protected]> | 2020-02-09 16:25:47 +0000 |
---|---|---|
committer | Kevin DeLorey <[email protected]> | 2020-02-09 16:37:43 +0000 |
commit | a957c473fdb79880c39b73dc9e0c923093cf16ac (patch) | |
tree | f998b548f530ce604651e0e6af314ed2ec74b3b5 /crates/ra_ide_db/src/line_index.rs | |
parent | 22caf982b99c54058e2e9200aeea0e61cada284a (diff) | |
parent | 1b9b13b4b4a75b5531c3f046ce6bf72d681f2732 (diff) |
Merge branch 'master' into kdelorey/complete-trait-impl
Diffstat (limited to 'crates/ra_ide_db/src/line_index.rs')
-rw-r--r-- | crates/ra_ide_db/src/line_index.rs | 284 |
1 files changed, 284 insertions, 0 deletions
diff --git a/crates/ra_ide_db/src/line_index.rs b/crates/ra_ide_db/src/line_index.rs new file mode 100644 index 000000000..452c87ac5 --- /dev/null +++ b/crates/ra_ide_db/src/line_index.rs | |||
@@ -0,0 +1,284 @@ | |||
1 | //! `LineIndex` maps flat `TextUnit` offsets into `(Line, Column)` | ||
2 | //! representation. | ||
3 | |||
4 | use ra_syntax::TextUnit; | ||
5 | use rustc_hash::FxHashMap; | ||
6 | use superslice::Ext; | ||
7 | |||
8 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
9 | pub struct LineIndex { | ||
10 | pub(crate) newlines: Vec<TextUnit>, | ||
11 | pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>, | ||
12 | } | ||
13 | |||
14 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] | ||
15 | pub struct LineCol { | ||
16 | /// Zero-based | ||
17 | pub line: u32, | ||
18 | /// Zero-based | ||
19 | pub col_utf16: u32, | ||
20 | } | ||
21 | |||
22 | #[derive(Clone, Debug, Hash, PartialEq, Eq)] | ||
23 | pub(crate) struct Utf16Char { | ||
24 | pub(crate) start: TextUnit, | ||
25 | pub(crate) end: TextUnit, | ||
26 | } | ||
27 | |||
28 | impl Utf16Char { | ||
29 | fn len(&self) -> TextUnit { | ||
30 | self.end - self.start | ||
31 | } | ||
32 | } | ||
33 | |||
34 | impl LineIndex { | ||
35 | pub fn new(text: &str) -> LineIndex { | ||
36 | let mut utf16_lines = FxHashMap::default(); | ||
37 | let mut utf16_chars = Vec::new(); | ||
38 | |||
39 | let mut newlines = vec![0.into()]; | ||
40 | let mut curr_row = 0.into(); | ||
41 | let mut curr_col = 0.into(); | ||
42 | let mut line = 0; | ||
43 | for c in text.chars() { | ||
44 | curr_row += TextUnit::of_char(c); | ||
45 | if c == '\n' { | ||
46 | newlines.push(curr_row); | ||
47 | |||
48 | // Save any utf-16 characters seen in the previous line | ||
49 | if !utf16_chars.is_empty() { | ||
50 | utf16_lines.insert(line, utf16_chars); | ||
51 | utf16_chars = Vec::new(); | ||
52 | } | ||
53 | |||
54 | // Prepare for processing the next line | ||
55 | curr_col = 0.into(); | ||
56 | line += 1; | ||
57 | continue; | ||
58 | } | ||
59 | |||
60 | let char_len = TextUnit::of_char(c); | ||
61 | if char_len.to_usize() > 1 { | ||
62 | utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len }); | ||
63 | } | ||
64 | |||
65 | curr_col += char_len; | ||
66 | } | ||
67 | |||
68 | // Save any utf-16 characters seen in the last line | ||
69 | if !utf16_chars.is_empty() { | ||
70 | utf16_lines.insert(line, utf16_chars); | ||
71 | } | ||
72 | |||
73 | LineIndex { newlines, utf16_lines } | ||
74 | } | ||
75 | |||
76 | pub fn line_col(&self, offset: TextUnit) -> LineCol { | ||
77 | let line = self.newlines.upper_bound(&offset) - 1; | ||
78 | let line_start_offset = self.newlines[line]; | ||
79 | let col = offset - line_start_offset; | ||
80 | |||
81 | LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 } | ||
82 | } | ||
83 | |||
84 | pub fn offset(&self, line_col: LineCol) -> TextUnit { | ||
85 | //FIXME: return Result | ||
86 | let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16); | ||
87 | self.newlines[line_col.line as usize] + col | ||
88 | } | ||
89 | |||
90 | fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize { | ||
91 | if let Some(utf16_chars) = self.utf16_lines.get(&line) { | ||
92 | let mut correction = TextUnit::from_usize(0); | ||
93 | for c in utf16_chars { | ||
94 | if col >= c.end { | ||
95 | correction += c.len() - TextUnit::from_usize(1); | ||
96 | } else { | ||
97 | // From here on, all utf16 characters come *after* the character we are mapping, | ||
98 | // so we don't need to take them into account | ||
99 | break; | ||
100 | } | ||
101 | } | ||
102 | |||
103 | col -= correction; | ||
104 | } | ||
105 | |||
106 | col.to_usize() | ||
107 | } | ||
108 | |||
109 | fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit { | ||
110 | let mut col: TextUnit = col.into(); | ||
111 | if let Some(utf16_chars) = self.utf16_lines.get(&line) { | ||
112 | for c in utf16_chars { | ||
113 | if col >= c.start { | ||
114 | col += c.len() - TextUnit::from_usize(1); | ||
115 | } else { | ||
116 | // From here on, all utf16 characters come *after* the character we are mapping, | ||
117 | // so we don't need to take them into account | ||
118 | break; | ||
119 | } | ||
120 | } | ||
121 | } | ||
122 | |||
123 | col | ||
124 | } | ||
125 | } | ||
126 | |||
127 | #[cfg(test)] | ||
128 | /// Simple reference implementation to use in proptests | ||
129 | pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol { | ||
130 | let mut res = LineCol { line: 0, col_utf16: 0 }; | ||
131 | for (i, c) in text.char_indices() { | ||
132 | if i + c.len_utf8() > offset.to_usize() { | ||
133 | // if it's an invalid offset, inside a multibyte char | ||
134 | // return as if it was at the start of the char | ||
135 | break; | ||
136 | } | ||
137 | if c == '\n' { | ||
138 | res.line += 1; | ||
139 | res.col_utf16 = 0; | ||
140 | } else { | ||
141 | res.col_utf16 += 1; | ||
142 | } | ||
143 | } | ||
144 | res | ||
145 | } | ||
146 | |||
147 | #[cfg(test)] | ||
148 | mod test_line_index { | ||
149 | use super::*; | ||
150 | use proptest::{prelude::*, proptest}; | ||
151 | use ra_text_edit::test_utils::{arb_offset, arb_text}; | ||
152 | |||
153 | #[test] | ||
154 | fn test_line_index() { | ||
155 | let text = "hello\nworld"; | ||
156 | let index = LineIndex::new(text); | ||
157 | assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 }); | ||
158 | assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 }); | ||
159 | assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 }); | ||
160 | assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 }); | ||
161 | assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 }); | ||
162 | assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 }); | ||
163 | assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 }); | ||
164 | assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 }); | ||
165 | assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 }); | ||
166 | |||
167 | let text = "\nhello\nworld"; | ||
168 | let index = LineIndex::new(text); | ||
169 | assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 }); | ||
170 | assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 }); | ||
171 | assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 }); | ||
172 | assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 }); | ||
173 | assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 }); | ||
174 | } | ||
175 | |||
176 | fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> { | ||
177 | arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed() | ||
178 | } | ||
179 | |||
180 | fn to_line_col(text: &str, offset: TextUnit) -> LineCol { | ||
181 | let mut res = LineCol { line: 0, col_utf16: 0 }; | ||
182 | for (i, c) in text.char_indices() { | ||
183 | if i + c.len_utf8() > offset.to_usize() { | ||
184 | // if it's an invalid offset, inside a multibyte char | ||
185 | // return as if it was at the start of the char | ||
186 | break; | ||
187 | } | ||
188 | if c == '\n' { | ||
189 | res.line += 1; | ||
190 | res.col_utf16 = 0; | ||
191 | } else { | ||
192 | res.col_utf16 += 1; | ||
193 | } | ||
194 | } | ||
195 | res | ||
196 | } | ||
197 | |||
198 | proptest! { | ||
199 | #[test] | ||
200 | fn test_line_index_proptest((offset, text) in arb_text_with_offset()) { | ||
201 | let expected = to_line_col(&text, offset); | ||
202 | let line_index = LineIndex::new(&text); | ||
203 | let actual = line_index.line_col(offset); | ||
204 | |||
205 | assert_eq!(actual, expected); | ||
206 | } | ||
207 | } | ||
208 | } | ||
209 | |||
210 | #[cfg(test)] | ||
211 | mod test_utf8_utf16_conv { | ||
212 | use super::*; | ||
213 | |||
214 | #[test] | ||
215 | fn test_char_len() { | ||
216 | assert_eq!('メ'.len_utf8(), 3); | ||
217 | assert_eq!('メ'.len_utf16(), 1); | ||
218 | } | ||
219 | |||
220 | #[test] | ||
221 | fn test_empty_index() { | ||
222 | let col_index = LineIndex::new( | ||
223 | " | ||
224 | const C: char = 'x'; | ||
225 | ", | ||
226 | ); | ||
227 | assert_eq!(col_index.utf16_lines.len(), 0); | ||
228 | } | ||
229 | |||
230 | #[test] | ||
231 | fn test_single_char() { | ||
232 | let col_index = LineIndex::new( | ||
233 | " | ||
234 | const C: char = 'メ'; | ||
235 | ", | ||
236 | ); | ||
237 | |||
238 | assert_eq!(col_index.utf16_lines.len(), 1); | ||
239 | assert_eq!(col_index.utf16_lines[&1].len(), 1); | ||
240 | assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() }); | ||
241 | |||
242 | // UTF-8 to UTF-16, no changes | ||
243 | assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15); | ||
244 | |||
245 | // UTF-8 to UTF-16 | ||
246 | assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20); | ||
247 | |||
248 | // UTF-16 to UTF-8, no changes | ||
249 | assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15)); | ||
250 | |||
251 | // UTF-16 to UTF-8 | ||
252 | assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21)); | ||
253 | } | ||
254 | |||
255 | #[test] | ||
256 | fn test_string() { | ||
257 | let col_index = LineIndex::new( | ||
258 | " | ||
259 | const C: char = \"メ メ\"; | ||
260 | ", | ||
261 | ); | ||
262 | |||
263 | assert_eq!(col_index.utf16_lines.len(), 1); | ||
264 | assert_eq!(col_index.utf16_lines[&1].len(), 2); | ||
265 | assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() }); | ||
266 | assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() }); | ||
267 | |||
268 | // UTF-8 to UTF-16 | ||
269 | assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15); | ||
270 | |||
271 | assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19); | ||
272 | assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21); | ||
273 | |||
274 | assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15); | ||
275 | |||
276 | // UTF-16 to UTF-8 | ||
277 | assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15)); | ||
278 | |||
279 | assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20)); | ||
280 | assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23)); | ||
281 | |||
282 | assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15)); | ||
283 | } | ||
284 | } | ||