aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_editor/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_editor/src')
-rw-r--r--crates/ra_editor/src/lib.rs2
-rw-r--r--crates/ra_editor/src/line_index.rs283
-rw-r--r--crates/ra_editor/src/line_index_utils.rs363
3 files changed, 544 insertions, 104 deletions
diff --git a/crates/ra_editor/src/lib.rs b/crates/ra_editor/src/lib.rs
index a8c68e79e..d9b89155b 100644
--- a/crates/ra_editor/src/lib.rs
+++ b/crates/ra_editor/src/lib.rs
@@ -2,6 +2,7 @@ mod code_actions;
2mod extend_selection; 2mod extend_selection;
3mod folding_ranges; 3mod folding_ranges;
4mod line_index; 4mod line_index;
5mod line_index_utils;
5mod symbols; 6mod symbols;
6#[cfg(test)] 7#[cfg(test)]
7mod test_utils; 8mod test_utils;
@@ -12,6 +13,7 @@ pub use self::{
12 extend_selection::extend_selection, 13 extend_selection::extend_selection,
13 folding_ranges::{folding_ranges, Fold, FoldKind}, 14 folding_ranges::{folding_ranges, Fold, FoldKind},
14 line_index::{LineCol, LineIndex}, 15 line_index::{LineCol, LineIndex},
16 line_index_utils::translate_offset_with_edit,
15 symbols::{file_structure, file_symbols, FileSymbol, StructureNode}, 17 symbols::{file_structure, file_symbols, FileSymbol, StructureNode},
16 typing::{join_lines, on_enter, on_eq_typed}, 18 typing::{join_lines, on_enter, on_eq_typed},
17}; 19};
diff --git a/crates/ra_editor/src/line_index.rs b/crates/ra_editor/src/line_index.rs
index aab7e4081..898fee7e0 100644
--- a/crates/ra_editor/src/line_index.rs
+++ b/crates/ra_editor/src/line_index.rs
@@ -4,8 +4,8 @@ use superslice::Ext;
4 4
5#[derive(Clone, Debug, PartialEq, Eq)] 5#[derive(Clone, Debug, PartialEq, Eq)]
6pub struct LineIndex { 6pub struct LineIndex {
7 newlines: Vec<TextUnit>, 7 pub(crate) newlines: Vec<TextUnit>,
8 utf16_lines: FxHashMap<u32, Vec<Utf16Char>>, 8 pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
9} 9}
10 10
11#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] 11#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
@@ -15,9 +15,9 @@ pub struct LineCol {
15} 15}
16 16
17#[derive(Clone, Debug, Hash, PartialEq, Eq)] 17#[derive(Clone, Debug, Hash, PartialEq, Eq)]
18struct Utf16Char { 18pub(crate) struct Utf16Char {
19 start: TextUnit, 19 pub(crate) start: TextUnit,
20 end: TextUnit, 20 pub(crate) end: TextUnit,
21} 21}
22 22
23impl Utf16Char { 23impl Utf16Char {
@@ -62,6 +62,12 @@ impl LineIndex {
62 62
63 curr_col += char_len; 63 curr_col += char_len;
64 } 64 }
65
66 // Save any utf-16 characters seen in the last line
67 if utf16_chars.len() > 0 {
68 utf16_lines.insert(line, utf16_chars);
69 }
70
65 LineIndex { 71 LineIndex {
66 newlines, 72 newlines,
67 utf16_lines, 73 utf16_lines,
@@ -122,111 +128,179 @@ impl LineIndex {
122 } 128 }
123} 129}
124 130
125#[test] 131#[cfg(test)]
126fn test_line_index() { 132/// Simple reference implementation to use in proptests
127 let text = "hello\nworld"; 133pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
128 let index = LineIndex::new(text); 134 let mut res = LineCol {
129 assert_eq!( 135 line: 0,
130 index.line_col(0.into()), 136 col_utf16: 0,
131 LineCol { 137 };
132 line: 0, 138 for (i, c) in text.char_indices() {
133 col_utf16: 0 139 if i + c.len_utf8() > offset.to_usize() {
134 } 140 // if it's an invalid offset, inside a multibyte char
135 ); 141 // return as if it was at the start of the char
136 assert_eq!( 142 break;
137 index.line_col(1.into()),
138 LineCol {
139 line: 0,
140 col_utf16: 1
141 }
142 );
143 assert_eq!(
144 index.line_col(5.into()),
145 LineCol {
146 line: 0,
147 col_utf16: 5
148 }
149 );
150 assert_eq!(
151 index.line_col(6.into()),
152 LineCol {
153 line: 1,
154 col_utf16: 0
155 }
156 );
157 assert_eq!(
158 index.line_col(7.into()),
159 LineCol {
160 line: 1,
161 col_utf16: 1
162 }
163 );
164 assert_eq!(
165 index.line_col(8.into()),
166 LineCol {
167 line: 1,
168 col_utf16: 2
169 }
170 );
171 assert_eq!(
172 index.line_col(10.into()),
173 LineCol {
174 line: 1,
175 col_utf16: 4
176 }
177 );
178 assert_eq!(
179 index.line_col(11.into()),
180 LineCol {
181 line: 1,
182 col_utf16: 5
183 } 143 }
184 ); 144 if c == '\n' {
185 assert_eq!( 145 res.line += 1;
186 index.line_col(12.into()), 146 res.col_utf16 = 0;
187 LineCol { 147 } else {
188 line: 1, 148 res.col_utf16 += 1;
189 col_utf16: 6
190 } 149 }
191 ); 150 }
151 res
152}
192 153
193 let text = "\nhello\nworld"; 154#[cfg(test)]
194 let index = LineIndex::new(text); 155mod test_line_index {
195 assert_eq!( 156 use super::*;
196 index.line_col(0.into()), 157 use proptest::{prelude::*, proptest, proptest_helper};
197 LineCol { 158 use ra_text_edit::test_utils::{arb_text, arb_offset};
159
160 #[test]
161 fn test_line_index() {
162 let text = "hello\nworld";
163 let index = LineIndex::new(text);
164 assert_eq!(
165 index.line_col(0.into()),
166 LineCol {
167 line: 0,
168 col_utf16: 0
169 }
170 );
171 assert_eq!(
172 index.line_col(1.into()),
173 LineCol {
174 line: 0,
175 col_utf16: 1
176 }
177 );
178 assert_eq!(
179 index.line_col(5.into()),
180 LineCol {
181 line: 0,
182 col_utf16: 5
183 }
184 );
185 assert_eq!(
186 index.line_col(6.into()),
187 LineCol {
188 line: 1,
189 col_utf16: 0
190 }
191 );
192 assert_eq!(
193 index.line_col(7.into()),
194 LineCol {
195 line: 1,
196 col_utf16: 1
197 }
198 );
199 assert_eq!(
200 index.line_col(8.into()),
201 LineCol {
202 line: 1,
203 col_utf16: 2
204 }
205 );
206 assert_eq!(
207 index.line_col(10.into()),
208 LineCol {
209 line: 1,
210 col_utf16: 4
211 }
212 );
213 assert_eq!(
214 index.line_col(11.into()),
215 LineCol {
216 line: 1,
217 col_utf16: 5
218 }
219 );
220 assert_eq!(
221 index.line_col(12.into()),
222 LineCol {
223 line: 1,
224 col_utf16: 6
225 }
226 );
227
228 let text = "\nhello\nworld";
229 let index = LineIndex::new(text);
230 assert_eq!(
231 index.line_col(0.into()),
232 LineCol {
233 line: 0,
234 col_utf16: 0
235 }
236 );
237 assert_eq!(
238 index.line_col(1.into()),
239 LineCol {
240 line: 1,
241 col_utf16: 0
242 }
243 );
244 assert_eq!(
245 index.line_col(2.into()),
246 LineCol {
247 line: 1,
248 col_utf16: 1
249 }
250 );
251 assert_eq!(
252 index.line_col(6.into()),
253 LineCol {
254 line: 1,
255 col_utf16: 5
256 }
257 );
258 assert_eq!(
259 index.line_col(7.into()),
260 LineCol {
261 line: 2,
262 col_utf16: 0
263 }
264 );
265 }
266
267 fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> {
268 arb_text()
269 .prop_flat_map(|text| (arb_offset(&text), Just(text)))
270 .boxed()
271 }
272
273 fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
274 let mut res = LineCol {
198 line: 0, 275 line: 0,
199 col_utf16: 0 276 col_utf16: 0,
200 } 277 };
201 ); 278 for (i, c) in text.char_indices() {
202 assert_eq!( 279 if i + c.len_utf8() > offset.to_usize() {
203 index.line_col(1.into()), 280 // if it's an invalid offset, inside a multibyte char
204 LineCol { 281 // return as if it was at the start of the char
205 line: 1, 282 break;
206 col_utf16: 0 283 }
207 } 284 if c == '\n' {
208 ); 285 res.line += 1;
209 assert_eq!( 286 res.col_utf16 = 0;
210 index.line_col(2.into()), 287 } else {
211 LineCol { 288 res.col_utf16 += 1;
212 line: 1, 289 }
213 col_utf16: 1
214 }
215 );
216 assert_eq!(
217 index.line_col(6.into()),
218 LineCol {
219 line: 1,
220 col_utf16: 5
221 } 290 }
222 ); 291 res
223 assert_eq!( 292 }
224 index.line_col(7.into()), 293
225 LineCol { 294 proptest! {
226 line: 2, 295 #[test]
227 col_utf16: 0 296 fn test_line_index_proptest((offset, text) in arb_text_with_offset()) {
297 let expected = to_line_col(&text, offset);
298 let line_index = LineIndex::new(&text);
299 let actual = line_index.line_col(offset);
300
301 assert_eq!(actual, expected);
228 } 302 }
229 ); 303 }
230} 304}
231 305
232#[cfg(test)] 306#[cfg(test)]
@@ -321,4 +395,5 @@ const C: char = \"メ メ\";
321 395
322 assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15)); 396 assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
323 } 397 }
398
324} 399}
diff --git a/crates/ra_editor/src/line_index_utils.rs b/crates/ra_editor/src/line_index_utils.rs
new file mode 100644
index 000000000..ec3269bbb
--- /dev/null
+++ b/crates/ra_editor/src/line_index_utils.rs
@@ -0,0 +1,363 @@
1use ra_text_edit::{AtomTextEdit, TextEdit};
2use ra_syntax::{TextUnit, TextRange};
3use crate::{LineIndex, LineCol, line_index::Utf16Char};
4
5#[derive(Debug, Clone)]
6enum Step {
7 Newline(TextUnit),
8 Utf16Char(TextRange),
9}
10
11#[derive(Debug)]
12struct LineIndexStepIter<'a> {
13 line_index: &'a LineIndex,
14 next_newline_idx: usize,
15 utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>,
16}
17
18impl<'a> LineIndexStepIter<'a> {
19 fn from(line_index: &LineIndex) -> LineIndexStepIter {
20 let mut x = LineIndexStepIter {
21 line_index,
22 next_newline_idx: 0,
23 utf16_chars: None,
24 };
25 // skip first newline since it's not real
26 x.next();
27 x
28 }
29}
30
31impl<'a> Iterator for LineIndexStepIter<'a> {
32 type Item = Step;
33 fn next(&mut self) -> Option<Step> {
34 self.utf16_chars
35 .as_mut()
36 .and_then(|(newline, x)| {
37 let x = x.next()?;
38 Some(Step::Utf16Char(TextRange::from_to(
39 *newline + x.start,
40 *newline + x.end,
41 )))
42 })
43 .or_else(|| {
44 let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?;
45 self.utf16_chars = self
46 .line_index
47 .utf16_lines
48 .get(&(self.next_newline_idx as u32))
49 .map(|x| (next_newline, x.iter()));
50 self.next_newline_idx += 1;
51 Some(Step::Newline(next_newline))
52 })
53 }
54}
55
56#[derive(Debug)]
57struct OffsetStepIter<'a> {
58 text: &'a str,
59 offset: TextUnit,
60}
61
62impl<'a> Iterator for OffsetStepIter<'a> {
63 type Item = Step;
64 fn next(&mut self) -> Option<Step> {
65 let (next, next_offset) = self
66 .text
67 .char_indices()
68 .filter_map(|(i, c)| {
69 if c == '\n' {
70 let next_offset = self.offset + TextUnit::from_usize(i + 1);
71 let next = Step::Newline(next_offset);
72 Some((next, next_offset))
73 } else {
74 let char_len = TextUnit::of_char(c);
75 if char_len.to_usize() > 1 {
76 let start = self.offset + TextUnit::from_usize(i);
77 let end = start + char_len;
78 let next = Step::Utf16Char(TextRange::from_to(start, end));
79 let next_offset = end;
80 Some((next, next_offset))
81 } else {
82 None
83 }
84 }
85 })
86 .next()?;
87 let next_idx = (next_offset - self.offset).to_usize();
88 self.text = &self.text[next_idx..];
89 self.offset = next_offset;
90 Some(next)
91 }
92}
93
94#[derive(Debug)]
95enum NextSteps<'a> {
96 Use,
97 ReplaceMany(OffsetStepIter<'a>),
98 AddMany(OffsetStepIter<'a>),
99}
100
101#[derive(Debug)]
102struct TranslatedEdit<'a> {
103 delete: TextRange,
104 insert: &'a str,
105 diff: i64,
106}
107
108struct Edits<'a> {
109 edits: &'a [AtomTextEdit],
110 current: Option<TranslatedEdit<'a>>,
111 acc_diff: i64,
112}
113
114impl<'a> Edits<'a> {
115 fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> {
116 let mut x = Edits {
117 edits: text_edit.as_atoms(),
118 current: None,
119 acc_diff: 0,
120 };
121 x.advance_edit();
122 x
123 }
124 fn advance_edit(&mut self) {
125 self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff);
126 match self.edits.split_first() {
127 Some((next, rest)) => {
128 let delete = self.translate_range(next.delete);
129 let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64;
130 self.current = Some(TranslatedEdit {
131 delete,
132 insert: &next.insert,
133 diff,
134 });
135 self.edits = rest;
136 }
137 None => {
138 self.current = None;
139 }
140 }
141 }
142
143 fn next_inserted_steps(&mut self) -> Option<OffsetStepIter<'a>> {
144 let cur = self.current.as_ref()?;
145 let res = Some(OffsetStepIter {
146 offset: cur.delete.start(),
147 text: &cur.insert,
148 });
149 self.advance_edit();
150 res
151 }
152
153 fn next_steps(&mut self, step: &Step) -> NextSteps {
154 let step_pos = match step {
155 &Step::Newline(n) => n,
156 &Step::Utf16Char(r) => r.end(),
157 };
158 let res = match &mut self.current {
159 Some(edit) => {
160 if step_pos <= edit.delete.start() {
161 NextSteps::Use
162 } else if step_pos <= edit.delete.end() {
163 let iter = OffsetStepIter {
164 offset: edit.delete.start(),
165 text: &edit.insert,
166 };
167 // empty slice to avoid returning steps again
168 edit.insert = &edit.insert[edit.insert.len()..];
169 NextSteps::ReplaceMany(iter)
170 } else {
171 let iter = OffsetStepIter {
172 offset: edit.delete.start(),
173 text: &edit.insert,
174 };
175 // empty slice to avoid returning steps again
176 edit.insert = &edit.insert[edit.insert.len()..];
177 self.advance_edit();
178 NextSteps::AddMany(iter)
179 }
180 }
181 None => NextSteps::Use,
182 };
183 res
184 }
185
186 fn translate_range(&self, range: TextRange) -> TextRange {
187 if self.acc_diff == 0 {
188 range
189 } else {
190 let start = self.translate(range.start());
191 let end = self.translate(range.end());
192 TextRange::from_to(start, end)
193 }
194 }
195
196 fn translate(&self, x: TextUnit) -> TextUnit {
197 if self.acc_diff == 0 {
198 x
199 } else {
200 TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32)
201 }
202 }
203
204 fn translate_step(&self, x: &Step) -> Step {
205 if self.acc_diff == 0 {
206 x.clone()
207 } else {
208 match x {
209 &Step::Newline(n) => Step::Newline(self.translate(n)),
210 &Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)),
211 }
212 }
213 }
214}
215
216#[derive(Debug)]
217struct RunningLineCol {
218 line: u32,
219 last_newline: TextUnit,
220 col_adjust: TextUnit,
221}
222
223impl RunningLineCol {
224 fn new() -> RunningLineCol {
225 RunningLineCol {
226 line: 0,
227 last_newline: TextUnit::from(0),
228 col_adjust: TextUnit::from(0),
229 }
230 }
231
232 fn to_line_col(&self, offset: TextUnit) -> LineCol {
233 LineCol {
234 line: self.line,
235 col_utf16: ((offset - self.last_newline) - self.col_adjust).into(),
236 }
237 }
238
239 fn add_line(&mut self, newline: TextUnit) {
240 self.line += 1;
241 self.last_newline = newline;
242 self.col_adjust = TextUnit::from(0);
243 }
244
245 fn adjust_col(&mut self, range: &TextRange) {
246 self.col_adjust += range.len() - TextUnit::from(1);
247 }
248}
249
250pub fn translate_offset_with_edit(
251 line_index: &LineIndex,
252 offset: TextUnit,
253 text_edit: &TextEdit,
254) -> LineCol {
255 let mut state = Edits::from_text_edit(&text_edit);
256
257 let mut res = RunningLineCol::new();
258
259 macro_rules! test_step {
260 ($x:ident) => {
261 match &$x {
262 Step::Newline(n) => {
263 if offset < *n {
264 return res.to_line_col(offset);
265 } else {
266 res.add_line(*n);
267 }
268 }
269 Step::Utf16Char(x) => {
270 if offset < x.end() {
271 // if the offset is inside a multibyte char it's invalid
272 // clamp it to the start of the char
273 let clamp = offset.min(x.start());
274 return res.to_line_col(clamp);
275 } else {
276 res.adjust_col(x);
277 }
278 }
279 }
280 };
281 }
282
283 for orig_step in LineIndexStepIter::from(line_index) {
284 loop {
285 let translated_step = state.translate_step(&orig_step);
286 match state.next_steps(&translated_step) {
287 NextSteps::Use => {
288 test_step!(translated_step);
289 break;
290 }
291 NextSteps::ReplaceMany(ns) => {
292 for n in ns {
293 test_step!(n);
294 }
295 break;
296 }
297 NextSteps::AddMany(ns) => {
298 for n in ns {
299 test_step!(n);
300 }
301 }
302 }
303 }
304 }
305
306 loop {
307 match state.next_inserted_steps() {
308 None => break,
309 Some(ns) => {
310 for n in ns {
311 test_step!(n);
312 }
313 }
314 }
315 }
316
317 res.to_line_col(offset)
318}
319
320#[cfg(test)]
321mod test {
322 use super::*;
323 use proptest::{prelude::*, proptest, proptest_helper};
324 use crate::line_index;
325 use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit};
326 use ra_text_edit::TextEdit;
327
328 #[derive(Debug)]
329 struct ArbTextWithEditAndOffset {
330 text: String,
331 edit: TextEdit,
332 edited_text: String,
333 offset: TextUnit,
334 }
335
336 fn arb_text_with_edit_and_offset() -> BoxedStrategy<ArbTextWithEditAndOffset> {
337 arb_text_with_edit()
338 .prop_flat_map(|x| {
339 let edited_text = x.edit.apply(&x.text);
340 let arb_offset = arb_offset(&edited_text);
341 (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| {
342 ArbTextWithEditAndOffset {
343 text: x.text,
344 edit: x.edit,
345 edited_text,
346 offset,
347 }
348 })
349 })
350 .boxed()
351 }
352
353 proptest! {
354 #[test]
355 fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) {
356 let expected = line_index::to_line_col(&x.edited_text, x.offset);
357 let line_index = LineIndex::new(&x.text);
358 let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit);
359
360 assert_eq!(actual, expected);
361 }
362 }
363}