From fda70badf8957eba6650cc12d2f485d5e213bb82 Mon Sep 17 00:00:00 2001 From: Sergey Parilin Date: Fri, 22 Mar 2019 15:24:43 +0300 Subject: line_index and line_index_utils moved to ra_ide_api --- Cargo.lock | 2 + crates/ra_ide_api/Cargo.toml | 2 + crates/ra_ide_api/src/lib.rs | 5 +- crates/ra_ide_api/src/line_index.rs | 280 ++++++++++++++++++++ crates/ra_ide_api/src/line_index_utils.rs | 330 ++++++++++++++++++++++++ crates/ra_ide_api_light/src/lib.rs | 4 - crates/ra_ide_api_light/src/line_index.rs | 280 -------------------- crates/ra_ide_api_light/src/line_index_utils.rs | 330 ------------------------ 8 files changed, 618 insertions(+), 615 deletions(-) create mode 100644 crates/ra_ide_api/src/line_index.rs create mode 100644 crates/ra_ide_api/src/line_index_utils.rs delete mode 100644 crates/ra_ide_api_light/src/line_index.rs delete mode 100644 crates/ra_ide_api_light/src/line_index_utils.rs diff --git a/Cargo.lock b/Cargo.lock index 50fe1fa23..9c7afe74b 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1005,6 +1005,7 @@ dependencies = [ "join_to_string 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)", "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)", "parking_lot 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)", + "proptest 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)", "ra_assists 0.1.0", "ra_db 0.1.0", "ra_hir 0.1.0", @@ -1014,6 +1015,7 @@ dependencies = [ "rayon 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)", "relative-path 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)", + "superslice 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)", "test_utils 0.1.0", "unicase 2.3.0 (registry+https://github.com/rust-lang/crates.io-index)", ] diff --git a/crates/ra_ide_api/Cargo.toml b/crates/ra_ide_api/Cargo.toml index 40b7a8d0a..ac8c8057b 100644 --- a/crates/ra_ide_api/Cargo.toml +++ b/crates/ra_ide_api/Cargo.toml @@ -14,6 +14,7 @@ fst = "0.3.1" rustc-hash = "1.0" parking_lot = "0.7.0" unicase = "2.2.0" +superslice = "1.0.0" jemallocator = { version = "0.1.9", optional = true } jemalloc-ctl = { version = "0.2.0", optional = true } @@ -28,6 +29,7 @@ ra_assists = { path = "../ra_assists" } [dev-dependencies] insta = "0.7.0" +proptest = "0.9.0" [features] jemalloc = [ "jemallocator", "jemalloc-ctl" ] diff --git a/crates/ra_ide_api/src/lib.rs b/crates/ra_ide_api/src/lib.rs index 81ca57035..35f38fbb7 100644 --- a/crates/ra_ide_api/src/lib.rs +++ b/crates/ra_ide_api/src/lib.rs @@ -33,6 +33,8 @@ mod impls; mod assists; mod diagnostics; mod syntax_tree; +mod line_index; +mod line_index_utils; #[cfg(test)] mod marks; @@ -60,10 +62,11 @@ pub use crate::{ references::ReferenceSearchResult, assists::{Assist, AssistId}, hover::{HoverResult}, + line_index::{LineIndex, LineCol}, + line_index_utils::translate_offset_with_edit, }; pub use ra_ide_api_light::{ Fold, FoldKind, HighlightedRange, Severity, StructureNode, LocalEdit, - LineIndex, LineCol, translate_offset_with_edit, }; pub use ra_db::{ Canceled, CrateGraph, CrateId, FileId, FilePosition, FileRange, SourceRootId, diff --git a/crates/ra_ide_api/src/line_index.rs b/crates/ra_ide_api/src/line_index.rs new file mode 100644 index 000000000..bf004c33a --- /dev/null +++ b/crates/ra_ide_api/src/line_index.rs @@ -0,0 +1,280 @@ +use crate::TextUnit; +use rustc_hash::FxHashMap; +use superslice::Ext; + +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct LineIndex { + pub(crate) newlines: Vec, + pub(crate) utf16_lines: FxHashMap>, +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct LineCol { + pub line: u32, + pub col_utf16: u32, +} + +#[derive(Clone, Debug, Hash, PartialEq, Eq)] +pub(crate) struct Utf16Char { + pub(crate) start: TextUnit, + pub(crate) end: TextUnit, +} + +impl Utf16Char { + fn len(&self) -> TextUnit { + self.end - self.start + } +} + +impl LineIndex { + pub fn new(text: &str) -> LineIndex { + let mut utf16_lines = FxHashMap::default(); + let mut utf16_chars = Vec::new(); + + let mut newlines = vec![0.into()]; + let mut curr_row = 0.into(); + let mut curr_col = 0.into(); + let mut line = 0; + for c in text.chars() { + curr_row += TextUnit::of_char(c); + if c == '\n' { + newlines.push(curr_row); + + // Save any utf-16 characters seen in the previous line + if utf16_chars.len() > 0 { + utf16_lines.insert(line, utf16_chars); + utf16_chars = Vec::new(); + } + + // Prepare for processing the next line + curr_col = 0.into(); + line += 1; + continue; + } + + let char_len = TextUnit::of_char(c); + if char_len.to_usize() > 1 { + utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len }); + } + + curr_col += char_len; + } + + // Save any utf-16 characters seen in the last line + if utf16_chars.len() > 0 { + utf16_lines.insert(line, utf16_chars); + } + + LineIndex { newlines, utf16_lines } + } + + pub fn line_col(&self, offset: TextUnit) -> LineCol { + let line = self.newlines.upper_bound(&offset) - 1; + let line_start_offset = self.newlines[line]; + let col = offset - line_start_offset; + + LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 } + } + + pub fn offset(&self, line_col: LineCol) -> TextUnit { + //TODO: return Result + let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16); + self.newlines[line_col.line as usize] + col + } + + fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize { + if let Some(utf16_chars) = self.utf16_lines.get(&line) { + let mut correction = TextUnit::from_usize(0); + for c in utf16_chars { + if col >= c.end { + correction += c.len() - TextUnit::from_usize(1); + } else { + // From here on, all utf16 characters come *after* the character we are mapping, + // so we don't need to take them into account + break; + } + } + + col -= correction; + } + + col.to_usize() + } + + fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit { + let mut col: TextUnit = col.into(); + if let Some(utf16_chars) = self.utf16_lines.get(&line) { + for c in utf16_chars { + if col >= c.start { + col += c.len() - TextUnit::from_usize(1); + } else { + // From here on, all utf16 characters come *after* the character we are mapping, + // so we don't need to take them into account + break; + } + } + } + + col + } +} + +#[cfg(test)] +/// Simple reference implementation to use in proptests +pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol { + let mut res = LineCol { line: 0, col_utf16: 0 }; + for (i, c) in text.char_indices() { + if i + c.len_utf8() > offset.to_usize() { + // if it's an invalid offset, inside a multibyte char + // return as if it was at the start of the char + break; + } + if c == '\n' { + res.line += 1; + res.col_utf16 = 0; + } else { + res.col_utf16 += 1; + } + } + res +} + +#[cfg(test)] +mod test_line_index { + use super::*; + use proptest::{prelude::*, proptest}; + use ra_text_edit::test_utils::{arb_text, arb_offset}; + + #[test] + fn test_line_index() { + let text = "hello\nworld"; + let index = LineIndex::new(text); + assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 }); + assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 }); + assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 }); + assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 }); + assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 }); + assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 }); + assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 }); + assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 }); + assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 }); + + let text = "\nhello\nworld"; + let index = LineIndex::new(text); + assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 }); + assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 }); + assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 }); + assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 }); + assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 }); + } + + fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> { + arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed() + } + + fn to_line_col(text: &str, offset: TextUnit) -> LineCol { + let mut res = LineCol { line: 0, col_utf16: 0 }; + for (i, c) in text.char_indices() { + if i + c.len_utf8() > offset.to_usize() { + // if it's an invalid offset, inside a multibyte char + // return as if it was at the start of the char + break; + } + if c == '\n' { + res.line += 1; + res.col_utf16 = 0; + } else { + res.col_utf16 += 1; + } + } + res + } + + proptest! { + #[test] + fn test_line_index_proptest((offset, text) in arb_text_with_offset()) { + let expected = to_line_col(&text, offset); + let line_index = LineIndex::new(&text); + let actual = line_index.line_col(offset); + + assert_eq!(actual, expected); + } + } +} + +#[cfg(test)] +mod test_utf8_utf16_conv { + use super::*; + + #[test] + fn test_char_len() { + assert_eq!('メ'.len_utf8(), 3); + assert_eq!('メ'.len_utf16(), 1); + } + + #[test] + fn test_empty_index() { + let col_index = LineIndex::new( + " +const C: char = 'x'; +", + ); + assert_eq!(col_index.utf16_lines.len(), 0); + } + + #[test] + fn test_single_char() { + let col_index = LineIndex::new( + " +const C: char = 'メ'; +", + ); + + assert_eq!(col_index.utf16_lines.len(), 1); + assert_eq!(col_index.utf16_lines[&1].len(), 1); + assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() }); + + // UTF-8 to UTF-16, no changes + assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15); + + // UTF-8 to UTF-16 + assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20); + + // UTF-16 to UTF-8, no changes + assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15)); + + // UTF-16 to UTF-8 + assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21)); + } + + #[test] + fn test_string() { + let col_index = LineIndex::new( + " +const C: char = \"メ メ\"; +", + ); + + assert_eq!(col_index.utf16_lines.len(), 1); + assert_eq!(col_index.utf16_lines[&1].len(), 2); + assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() }); + assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() }); + + // UTF-8 to UTF-16 + assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15); + + assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19); + assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21); + + assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15); + + // UTF-16 to UTF-8 + assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15)); + + assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20)); + assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23)); + + assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15)); + } + +} diff --git a/crates/ra_ide_api/src/line_index_utils.rs b/crates/ra_ide_api/src/line_index_utils.rs new file mode 100644 index 000000000..799a920ad --- /dev/null +++ b/crates/ra_ide_api/src/line_index_utils.rs @@ -0,0 +1,330 @@ +use ra_text_edit::{AtomTextEdit, TextEdit}; +use ra_syntax::{TextUnit, TextRange}; +use crate::{LineIndex, LineCol, line_index::Utf16Char}; + +#[derive(Debug, Clone)] +enum Step { + Newline(TextUnit), + Utf16Char(TextRange), +} + +#[derive(Debug)] +struct LineIndexStepIter<'a> { + line_index: &'a LineIndex, + next_newline_idx: usize, + utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>, +} + +impl<'a> LineIndexStepIter<'a> { + fn from(line_index: &LineIndex) -> LineIndexStepIter { + let mut x = LineIndexStepIter { line_index, next_newline_idx: 0, utf16_chars: None }; + // skip first newline since it's not real + x.next(); + x + } +} + +impl<'a> Iterator for LineIndexStepIter<'a> { + type Item = Step; + fn next(&mut self) -> Option { + self.utf16_chars + .as_mut() + .and_then(|(newline, x)| { + let x = x.next()?; + Some(Step::Utf16Char(TextRange::from_to(*newline + x.start, *newline + x.end))) + }) + .or_else(|| { + let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?; + self.utf16_chars = self + .line_index + .utf16_lines + .get(&(self.next_newline_idx as u32)) + .map(|x| (next_newline, x.iter())); + self.next_newline_idx += 1; + Some(Step::Newline(next_newline)) + }) + } +} + +#[derive(Debug)] +struct OffsetStepIter<'a> { + text: &'a str, + offset: TextUnit, +} + +impl<'a> Iterator for OffsetStepIter<'a> { + type Item = Step; + fn next(&mut self) -> Option { + let (next, next_offset) = self + .text + .char_indices() + .filter_map(|(i, c)| { + if c == '\n' { + let next_offset = self.offset + TextUnit::from_usize(i + 1); + let next = Step::Newline(next_offset); + Some((next, next_offset)) + } else { + let char_len = TextUnit::of_char(c); + if char_len.to_usize() > 1 { + let start = self.offset + TextUnit::from_usize(i); + let end = start + char_len; + let next = Step::Utf16Char(TextRange::from_to(start, end)); + let next_offset = end; + Some((next, next_offset)) + } else { + None + } + } + }) + .next()?; + let next_idx = (next_offset - self.offset).to_usize(); + self.text = &self.text[next_idx..]; + self.offset = next_offset; + Some(next) + } +} + +#[derive(Debug)] +enum NextSteps<'a> { + Use, + ReplaceMany(OffsetStepIter<'a>), + AddMany(OffsetStepIter<'a>), +} + +#[derive(Debug)] +struct TranslatedEdit<'a> { + delete: TextRange, + insert: &'a str, + diff: i64, +} + +struct Edits<'a> { + edits: &'a [AtomTextEdit], + current: Option>, + acc_diff: i64, +} + +impl<'a> Edits<'a> { + fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> { + let mut x = Edits { edits: text_edit.as_atoms(), current: None, acc_diff: 0 }; + x.advance_edit(); + x + } + fn advance_edit(&mut self) { + self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff); + match self.edits.split_first() { + Some((next, rest)) => { + let delete = self.translate_range(next.delete); + let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64; + self.current = Some(TranslatedEdit { delete, insert: &next.insert, diff }); + self.edits = rest; + } + None => { + self.current = None; + } + } + } + + fn next_inserted_steps(&mut self) -> Option> { + let cur = self.current.as_ref()?; + let res = Some(OffsetStepIter { offset: cur.delete.start(), text: &cur.insert }); + self.advance_edit(); + res + } + + fn next_steps(&mut self, step: &Step) -> NextSteps { + let step_pos = match step { + &Step::Newline(n) => n, + &Step::Utf16Char(r) => r.end(), + }; + let res = match &mut self.current { + Some(edit) => { + if step_pos <= edit.delete.start() { + NextSteps::Use + } else if step_pos <= edit.delete.end() { + let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert }; + // empty slice to avoid returning steps again + edit.insert = &edit.insert[edit.insert.len()..]; + NextSteps::ReplaceMany(iter) + } else { + let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert }; + // empty slice to avoid returning steps again + edit.insert = &edit.insert[edit.insert.len()..]; + self.advance_edit(); + NextSteps::AddMany(iter) + } + } + None => NextSteps::Use, + }; + res + } + + fn translate_range(&self, range: TextRange) -> TextRange { + if self.acc_diff == 0 { + range + } else { + let start = self.translate(range.start()); + let end = self.translate(range.end()); + TextRange::from_to(start, end) + } + } + + fn translate(&self, x: TextUnit) -> TextUnit { + if self.acc_diff == 0 { + x + } else { + TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32) + } + } + + fn translate_step(&self, x: &Step) -> Step { + if self.acc_diff == 0 { + x.clone() + } else { + match x { + &Step::Newline(n) => Step::Newline(self.translate(n)), + &Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)), + } + } + } +} + +#[derive(Debug)] +struct RunningLineCol { + line: u32, + last_newline: TextUnit, + col_adjust: TextUnit, +} + +impl RunningLineCol { + fn new() -> RunningLineCol { + RunningLineCol { line: 0, last_newline: TextUnit::from(0), col_adjust: TextUnit::from(0) } + } + + fn to_line_col(&self, offset: TextUnit) -> LineCol { + LineCol { + line: self.line, + col_utf16: ((offset - self.last_newline) - self.col_adjust).into(), + } + } + + fn add_line(&mut self, newline: TextUnit) { + self.line += 1; + self.last_newline = newline; + self.col_adjust = TextUnit::from(0); + } + + fn adjust_col(&mut self, range: &TextRange) { + self.col_adjust += range.len() - TextUnit::from(1); + } +} + +pub fn translate_offset_with_edit( + line_index: &LineIndex, + offset: TextUnit, + text_edit: &TextEdit, +) -> LineCol { + let mut state = Edits::from_text_edit(&text_edit); + + let mut res = RunningLineCol::new(); + + macro_rules! test_step { + ($x:ident) => { + match &$x { + Step::Newline(n) => { + if offset < *n { + return res.to_line_col(offset); + } else { + res.add_line(*n); + } + } + Step::Utf16Char(x) => { + if offset < x.end() { + // if the offset is inside a multibyte char it's invalid + // clamp it to the start of the char + let clamp = offset.min(x.start()); + return res.to_line_col(clamp); + } else { + res.adjust_col(x); + } + } + } + }; + } + + for orig_step in LineIndexStepIter::from(line_index) { + loop { + let translated_step = state.translate_step(&orig_step); + match state.next_steps(&translated_step) { + NextSteps::Use => { + test_step!(translated_step); + break; + } + NextSteps::ReplaceMany(ns) => { + for n in ns { + test_step!(n); + } + break; + } + NextSteps::AddMany(ns) => { + for n in ns { + test_step!(n); + } + } + } + } + } + + loop { + match state.next_inserted_steps() { + None => break, + Some(ns) => { + for n in ns { + test_step!(n); + } + } + } + } + + res.to_line_col(offset) +} + +#[cfg(test)] +mod test { + use super::*; + use proptest::{prelude::*, proptest}; + use crate::line_index; + use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit}; + use ra_text_edit::TextEdit; + + #[derive(Debug)] + struct ArbTextWithEditAndOffset { + text: String, + edit: TextEdit, + edited_text: String, + offset: TextUnit, + } + + fn arb_text_with_edit_and_offset() -> BoxedStrategy { + arb_text_with_edit() + .prop_flat_map(|x| { + let edited_text = x.edit.apply(&x.text); + let arb_offset = arb_offset(&edited_text); + (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| { + ArbTextWithEditAndOffset { text: x.text, edit: x.edit, edited_text, offset } + }) + }) + .boxed() + } + + proptest! { + #[test] + fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) { + let expected = line_index::to_line_col(&x.edited_text, x.offset); + let line_index = LineIndex::new(&x.text); + let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit); + + assert_eq!(actual, expected); + } + } +} diff --git a/crates/ra_ide_api_light/src/lib.rs b/crates/ra_ide_api_light/src/lib.rs index 47b30255b..556d44c25 100644 --- a/crates/ra_ide_api_light/src/lib.rs +++ b/crates/ra_ide_api_light/src/lib.rs @@ -4,8 +4,6 @@ //! an edit or some auxiliary info. mod folding_ranges; -mod line_index; -mod line_index_utils; mod structure; #[cfg(test)] mod test_utils; @@ -23,8 +21,6 @@ use ra_syntax::{ pub use crate::{ folding_ranges::{folding_ranges, Fold, FoldKind}, - line_index::{LineCol, LineIndex}, - line_index_utils::translate_offset_with_edit, structure::{file_structure, StructureNode}, join_lines::join_lines, typing::{on_enter, on_dot_typed, on_eq_typed}, diff --git a/crates/ra_ide_api_light/src/line_index.rs b/crates/ra_ide_api_light/src/line_index.rs deleted file mode 100644 index bf004c33a..000000000 --- a/crates/ra_ide_api_light/src/line_index.rs +++ /dev/null @@ -1,280 +0,0 @@ -use crate::TextUnit; -use rustc_hash::FxHashMap; -use superslice::Ext; - -#[derive(Clone, Debug, PartialEq, Eq)] -pub struct LineIndex { - pub(crate) newlines: Vec, - pub(crate) utf16_lines: FxHashMap>, -} - -#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] -pub struct LineCol { - pub line: u32, - pub col_utf16: u32, -} - -#[derive(Clone, Debug, Hash, PartialEq, Eq)] -pub(crate) struct Utf16Char { - pub(crate) start: TextUnit, - pub(crate) end: TextUnit, -} - -impl Utf16Char { - fn len(&self) -> TextUnit { - self.end - self.start - } -} - -impl LineIndex { - pub fn new(text: &str) -> LineIndex { - let mut utf16_lines = FxHashMap::default(); - let mut utf16_chars = Vec::new(); - - let mut newlines = vec![0.into()]; - let mut curr_row = 0.into(); - let mut curr_col = 0.into(); - let mut line = 0; - for c in text.chars() { - curr_row += TextUnit::of_char(c); - if c == '\n' { - newlines.push(curr_row); - - // Save any utf-16 characters seen in the previous line - if utf16_chars.len() > 0 { - utf16_lines.insert(line, utf16_chars); - utf16_chars = Vec::new(); - } - - // Prepare for processing the next line - curr_col = 0.into(); - line += 1; - continue; - } - - let char_len = TextUnit::of_char(c); - if char_len.to_usize() > 1 { - utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len }); - } - - curr_col += char_len; - } - - // Save any utf-16 characters seen in the last line - if utf16_chars.len() > 0 { - utf16_lines.insert(line, utf16_chars); - } - - LineIndex { newlines, utf16_lines } - } - - pub fn line_col(&self, offset: TextUnit) -> LineCol { - let line = self.newlines.upper_bound(&offset) - 1; - let line_start_offset = self.newlines[line]; - let col = offset - line_start_offset; - - LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 } - } - - pub fn offset(&self, line_col: LineCol) -> TextUnit { - //TODO: return Result - let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16); - self.newlines[line_col.line as usize] + col - } - - fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize { - if let Some(utf16_chars) = self.utf16_lines.get(&line) { - let mut correction = TextUnit::from_usize(0); - for c in utf16_chars { - if col >= c.end { - correction += c.len() - TextUnit::from_usize(1); - } else { - // From here on, all utf16 characters come *after* the character we are mapping, - // so we don't need to take them into account - break; - } - } - - col -= correction; - } - - col.to_usize() - } - - fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit { - let mut col: TextUnit = col.into(); - if let Some(utf16_chars) = self.utf16_lines.get(&line) { - for c in utf16_chars { - if col >= c.start { - col += c.len() - TextUnit::from_usize(1); - } else { - // From here on, all utf16 characters come *after* the character we are mapping, - // so we don't need to take them into account - break; - } - } - } - - col - } -} - -#[cfg(test)] -/// Simple reference implementation to use in proptests -pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol { - let mut res = LineCol { line: 0, col_utf16: 0 }; - for (i, c) in text.char_indices() { - if i + c.len_utf8() > offset.to_usize() { - // if it's an invalid offset, inside a multibyte char - // return as if it was at the start of the char - break; - } - if c == '\n' { - res.line += 1; - res.col_utf16 = 0; - } else { - res.col_utf16 += 1; - } - } - res -} - -#[cfg(test)] -mod test_line_index { - use super::*; - use proptest::{prelude::*, proptest}; - use ra_text_edit::test_utils::{arb_text, arb_offset}; - - #[test] - fn test_line_index() { - let text = "hello\nworld"; - let index = LineIndex::new(text); - assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 }); - assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 }); - assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 }); - assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 }); - assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 }); - assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 }); - assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 }); - assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 }); - assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 }); - - let text = "\nhello\nworld"; - let index = LineIndex::new(text); - assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 }); - assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 }); - assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 }); - assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 }); - assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 }); - } - - fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> { - arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed() - } - - fn to_line_col(text: &str, offset: TextUnit) -> LineCol { - let mut res = LineCol { line: 0, col_utf16: 0 }; - for (i, c) in text.char_indices() { - if i + c.len_utf8() > offset.to_usize() { - // if it's an invalid offset, inside a multibyte char - // return as if it was at the start of the char - break; - } - if c == '\n' { - res.line += 1; - res.col_utf16 = 0; - } else { - res.col_utf16 += 1; - } - } - res - } - - proptest! { - #[test] - fn test_line_index_proptest((offset, text) in arb_text_with_offset()) { - let expected = to_line_col(&text, offset); - let line_index = LineIndex::new(&text); - let actual = line_index.line_col(offset); - - assert_eq!(actual, expected); - } - } -} - -#[cfg(test)] -mod test_utf8_utf16_conv { - use super::*; - - #[test] - fn test_char_len() { - assert_eq!('メ'.len_utf8(), 3); - assert_eq!('メ'.len_utf16(), 1); - } - - #[test] - fn test_empty_index() { - let col_index = LineIndex::new( - " -const C: char = 'x'; -", - ); - assert_eq!(col_index.utf16_lines.len(), 0); - } - - #[test] - fn test_single_char() { - let col_index = LineIndex::new( - " -const C: char = 'メ'; -", - ); - - assert_eq!(col_index.utf16_lines.len(), 1); - assert_eq!(col_index.utf16_lines[&1].len(), 1); - assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() }); - - // UTF-8 to UTF-16, no changes - assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15); - - // UTF-8 to UTF-16 - assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20); - - // UTF-16 to UTF-8, no changes - assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15)); - - // UTF-16 to UTF-8 - assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21)); - } - - #[test] - fn test_string() { - let col_index = LineIndex::new( - " -const C: char = \"メ メ\"; -", - ); - - assert_eq!(col_index.utf16_lines.len(), 1); - assert_eq!(col_index.utf16_lines[&1].len(), 2); - assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() }); - assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() }); - - // UTF-8 to UTF-16 - assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15); - - assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19); - assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21); - - assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15); - - // UTF-16 to UTF-8 - assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15)); - - assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20)); - assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23)); - - assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15)); - } - -} diff --git a/crates/ra_ide_api_light/src/line_index_utils.rs b/crates/ra_ide_api_light/src/line_index_utils.rs deleted file mode 100644 index 799a920ad..000000000 --- a/crates/ra_ide_api_light/src/line_index_utils.rs +++ /dev/null @@ -1,330 +0,0 @@ -use ra_text_edit::{AtomTextEdit, TextEdit}; -use ra_syntax::{TextUnit, TextRange}; -use crate::{LineIndex, LineCol, line_index::Utf16Char}; - -#[derive(Debug, Clone)] -enum Step { - Newline(TextUnit), - Utf16Char(TextRange), -} - -#[derive(Debug)] -struct LineIndexStepIter<'a> { - line_index: &'a LineIndex, - next_newline_idx: usize, - utf16_chars: Option<(TextUnit, std::slice::Iter<'a, Utf16Char>)>, -} - -impl<'a> LineIndexStepIter<'a> { - fn from(line_index: &LineIndex) -> LineIndexStepIter { - let mut x = LineIndexStepIter { line_index, next_newline_idx: 0, utf16_chars: None }; - // skip first newline since it's not real - x.next(); - x - } -} - -impl<'a> Iterator for LineIndexStepIter<'a> { - type Item = Step; - fn next(&mut self) -> Option { - self.utf16_chars - .as_mut() - .and_then(|(newline, x)| { - let x = x.next()?; - Some(Step::Utf16Char(TextRange::from_to(*newline + x.start, *newline + x.end))) - }) - .or_else(|| { - let next_newline = *self.line_index.newlines.get(self.next_newline_idx)?; - self.utf16_chars = self - .line_index - .utf16_lines - .get(&(self.next_newline_idx as u32)) - .map(|x| (next_newline, x.iter())); - self.next_newline_idx += 1; - Some(Step::Newline(next_newline)) - }) - } -} - -#[derive(Debug)] -struct OffsetStepIter<'a> { - text: &'a str, - offset: TextUnit, -} - -impl<'a> Iterator for OffsetStepIter<'a> { - type Item = Step; - fn next(&mut self) -> Option { - let (next, next_offset) = self - .text - .char_indices() - .filter_map(|(i, c)| { - if c == '\n' { - let next_offset = self.offset + TextUnit::from_usize(i + 1); - let next = Step::Newline(next_offset); - Some((next, next_offset)) - } else { - let char_len = TextUnit::of_char(c); - if char_len.to_usize() > 1 { - let start = self.offset + TextUnit::from_usize(i); - let end = start + char_len; - let next = Step::Utf16Char(TextRange::from_to(start, end)); - let next_offset = end; - Some((next, next_offset)) - } else { - None - } - } - }) - .next()?; - let next_idx = (next_offset - self.offset).to_usize(); - self.text = &self.text[next_idx..]; - self.offset = next_offset; - Some(next) - } -} - -#[derive(Debug)] -enum NextSteps<'a> { - Use, - ReplaceMany(OffsetStepIter<'a>), - AddMany(OffsetStepIter<'a>), -} - -#[derive(Debug)] -struct TranslatedEdit<'a> { - delete: TextRange, - insert: &'a str, - diff: i64, -} - -struct Edits<'a> { - edits: &'a [AtomTextEdit], - current: Option>, - acc_diff: i64, -} - -impl<'a> Edits<'a> { - fn from_text_edit(text_edit: &'a TextEdit) -> Edits<'a> { - let mut x = Edits { edits: text_edit.as_atoms(), current: None, acc_diff: 0 }; - x.advance_edit(); - x - } - fn advance_edit(&mut self) { - self.acc_diff += self.current.as_ref().map_or(0, |x| x.diff); - match self.edits.split_first() { - Some((next, rest)) => { - let delete = self.translate_range(next.delete); - let diff = next.insert.len() as i64 - next.delete.len().to_usize() as i64; - self.current = Some(TranslatedEdit { delete, insert: &next.insert, diff }); - self.edits = rest; - } - None => { - self.current = None; - } - } - } - - fn next_inserted_steps(&mut self) -> Option> { - let cur = self.current.as_ref()?; - let res = Some(OffsetStepIter { offset: cur.delete.start(), text: &cur.insert }); - self.advance_edit(); - res - } - - fn next_steps(&mut self, step: &Step) -> NextSteps { - let step_pos = match step { - &Step::Newline(n) => n, - &Step::Utf16Char(r) => r.end(), - }; - let res = match &mut self.current { - Some(edit) => { - if step_pos <= edit.delete.start() { - NextSteps::Use - } else if step_pos <= edit.delete.end() { - let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert }; - // empty slice to avoid returning steps again - edit.insert = &edit.insert[edit.insert.len()..]; - NextSteps::ReplaceMany(iter) - } else { - let iter = OffsetStepIter { offset: edit.delete.start(), text: &edit.insert }; - // empty slice to avoid returning steps again - edit.insert = &edit.insert[edit.insert.len()..]; - self.advance_edit(); - NextSteps::AddMany(iter) - } - } - None => NextSteps::Use, - }; - res - } - - fn translate_range(&self, range: TextRange) -> TextRange { - if self.acc_diff == 0 { - range - } else { - let start = self.translate(range.start()); - let end = self.translate(range.end()); - TextRange::from_to(start, end) - } - } - - fn translate(&self, x: TextUnit) -> TextUnit { - if self.acc_diff == 0 { - x - } else { - TextUnit::from((x.to_usize() as i64 + self.acc_diff) as u32) - } - } - - fn translate_step(&self, x: &Step) -> Step { - if self.acc_diff == 0 { - x.clone() - } else { - match x { - &Step::Newline(n) => Step::Newline(self.translate(n)), - &Step::Utf16Char(r) => Step::Utf16Char(self.translate_range(r)), - } - } - } -} - -#[derive(Debug)] -struct RunningLineCol { - line: u32, - last_newline: TextUnit, - col_adjust: TextUnit, -} - -impl RunningLineCol { - fn new() -> RunningLineCol { - RunningLineCol { line: 0, last_newline: TextUnit::from(0), col_adjust: TextUnit::from(0) } - } - - fn to_line_col(&self, offset: TextUnit) -> LineCol { - LineCol { - line: self.line, - col_utf16: ((offset - self.last_newline) - self.col_adjust).into(), - } - } - - fn add_line(&mut self, newline: TextUnit) { - self.line += 1; - self.last_newline = newline; - self.col_adjust = TextUnit::from(0); - } - - fn adjust_col(&mut self, range: &TextRange) { - self.col_adjust += range.len() - TextUnit::from(1); - } -} - -pub fn translate_offset_with_edit( - line_index: &LineIndex, - offset: TextUnit, - text_edit: &TextEdit, -) -> LineCol { - let mut state = Edits::from_text_edit(&text_edit); - - let mut res = RunningLineCol::new(); - - macro_rules! test_step { - ($x:ident) => { - match &$x { - Step::Newline(n) => { - if offset < *n { - return res.to_line_col(offset); - } else { - res.add_line(*n); - } - } - Step::Utf16Char(x) => { - if offset < x.end() { - // if the offset is inside a multibyte char it's invalid - // clamp it to the start of the char - let clamp = offset.min(x.start()); - return res.to_line_col(clamp); - } else { - res.adjust_col(x); - } - } - } - }; - } - - for orig_step in LineIndexStepIter::from(line_index) { - loop { - let translated_step = state.translate_step(&orig_step); - match state.next_steps(&translated_step) { - NextSteps::Use => { - test_step!(translated_step); - break; - } - NextSteps::ReplaceMany(ns) => { - for n in ns { - test_step!(n); - } - break; - } - NextSteps::AddMany(ns) => { - for n in ns { - test_step!(n); - } - } - } - } - } - - loop { - match state.next_inserted_steps() { - None => break, - Some(ns) => { - for n in ns { - test_step!(n); - } - } - } - } - - res.to_line_col(offset) -} - -#[cfg(test)] -mod test { - use super::*; - use proptest::{prelude::*, proptest}; - use crate::line_index; - use ra_text_edit::test_utils::{arb_offset, arb_text_with_edit}; - use ra_text_edit::TextEdit; - - #[derive(Debug)] - struct ArbTextWithEditAndOffset { - text: String, - edit: TextEdit, - edited_text: String, - offset: TextUnit, - } - - fn arb_text_with_edit_and_offset() -> BoxedStrategy { - arb_text_with_edit() - .prop_flat_map(|x| { - let edited_text = x.edit.apply(&x.text); - let arb_offset = arb_offset(&edited_text); - (Just(x), Just(edited_text), arb_offset).prop_map(|(x, edited_text, offset)| { - ArbTextWithEditAndOffset { text: x.text, edit: x.edit, edited_text, offset } - }) - }) - .boxed() - } - - proptest! { - #[test] - fn test_translate_offset_with_edit(x in arb_text_with_edit_and_offset()) { - let expected = line_index::to_line_col(&x.edited_text, x.offset); - let line_index = LineIndex::new(&x.text); - let actual = translate_offset_with_edit(&line_index, x.offset, &x.edit); - - assert_eq!(actual, expected); - } - } -} -- cgit v1.2.3