use std::ops::Range as ByteRange;
use gen_lsp_types::*;
use crate::error::ErrorKind;
fn units(encoding: &PositionEncodingKind, c: char) -> u32 {
match encoding {
PositionEncodingKind::UTF8 => u32::try_from(c.len_utf8()).unwrap(),
PositionEncodingKind::UTF16 => u32::try_from(c.len_utf16()).unwrap(),
_ => 1,
}
}
fn span(text: &str, range: Range, encoding: &PositionEncodingKind) -> Option<ByteRange<usize>> {
let start = offset(text, range.start, encoding)?;
let end = offset(text, range.end, encoding)?;
(start <= end).then_some(start..end)
}
fn line_end(text: &str, from: usize) -> Option<(usize, usize)> {
let end = from + text[from..].find(['\n', '\r'])?;
let terminator = if text[end..].starts_with("\r\n") {
2
} else {
1
};
Some((end, end + terminator))
}
fn offset(text: &str, position: Position, encoding: &PositionEncodingKind) -> Option<usize> {
let mut start = 0;
for _ in 0..position.line {
match line_end(text, start) {
Some((_, next)) => start = next,
None => return Some(text.len()),
}
}
let end = line_end(text, start).map_or(text.len(), |(end, _)| end);
let mut count = 0;
for (index, c) in text[start..end].char_indices() {
if count == position.character {
return Some(start + index);
}
count += units(encoding, c);
if count > position.character {
return None;
}
}
Some(end)
}
fn position(text: &str, offset: usize, encoding: &PositionEncodingKind) -> Position {
let mut line = 0;
let mut start = 0;
while let Some((_, next)) = line_end(text, start)
&& next <= offset
{
line += 1;
start = next;
}
let character = text[start..offset]
.chars()
.map(|c| units(encoding, c))
.sum();
Position::new(line, character)
}
fn spans(
text: &str,
edits: &[TextEdit],
encoding: &PositionEncodingKind,
) -> crate::Result<Vec<(std::ops::Range<usize>, usize)>> {
let mut spans = edits
.iter()
.enumerate()
.map(|(index, edit)| {
span(text, edit.range, encoding)
.map(|range| (range, index))
.ok_or_else(|| {
ErrorKind::InvalidEdit {
index,
range: edit.range,
}
.into()
})
})
.collect::<crate::Result<Vec<_>>>()?;
spans.sort_unstable_by_key(|(range, index)| (range.start, range.end, *index));
if spans.windows(2).any(|pair| {
let [a, b] = pair else { return false };
a.0.contains(&b.0.start)
}) {
return Err(ErrorKind::OverlappingEdits.into());
}
Ok(spans)
}
fn splice(
text: &str,
edits: &[TextEdit],
spans: &[(std::ops::Range<usize>, usize)],
from: usize,
to: usize,
) -> String {
let mut result = String::with_capacity(to - from);
let mut last = from;
for (range, index) in spans {
result.push_str(&text[last..range.start]);
result.push_str(&edits[*index].new_text);
last = range.end;
}
result.push_str(&text[last..to]);
result
}
pub(crate) fn apply(
text: &str,
edits: &[TextEdit],
encoding: &PositionEncodingKind,
) -> crate::Result<String> {
let spans = spans(text, edits, encoding)?;
Ok(splice(text, edits, &spans, 0, text.len()))
}
pub(crate) fn changes(
text: &str,
edits: &[TextEdit],
encoding: &PositionEncodingKind,
) -> crate::Result<Vec<TextDocumentContentChangeEvent>> {
let spans = spans(text, edits, encoding)?;
let (Some((first, _)), Some((last, _))) = (spans.first(), spans.last()) else {
return Ok(Vec::new());
};
let (start, end) = (first.start, last.end);
let replaced = splice(text, edits, &spans, start, end);
Ok(vec![
TextDocumentContentChangePartial::new(
Range::new(
position(text, start, encoding),
position(text, end, encoding),
),
None,
replaced,
)
.into(),
])
}
pub(crate) fn apply_changes(
text: &str,
changes: &[TextDocumentContentChangeEvent],
encoding: &PositionEncodingKind,
) -> crate::Result<String> {
let mut result = text.to_owned();
for (index, change) in changes.iter().enumerate() {
match change {
TextDocumentContentChangeEvent::TextDocumentContentChangeWholeDocument(whole) => {
result.clone_from(&whole.text);
}
TextDocumentContentChangeEvent::TextDocumentContentChangePartial(partial) => {
let Some(range) = span(&result, partial.range, encoding) else {
return Err(ErrorKind::InvalidEdit {
index,
range: partial.range,
}
.into());
};
result.replace_range(range, &partial.text);
}
}
}
Ok(result)
}
#[cfg(test)]
mod tests {
use super::*;
fn at(line: u32, character: u32) -> Position {
Position::new(line, character)
}
fn edit(start: (u32, u32), end: (u32, u32), new_text: &str) -> TextEdit {
TextEdit {
range: Range::new(at(start.0, start.1), at(end.0, end.1)),
new_text: new_text.to_owned(),
}
}
fn whole(text: &str) -> TextDocumentContentChangeEvent {
gen_lsp_types::TextDocumentContentChangeWholeDocument {
text: text.to_owned(),
}
.into()
}
fn partial(start: (u32, u32), end: (u32, u32), text: &str) -> TextDocumentContentChangeEvent {
TextDocumentContentChangePartial::new(
Range::new(at(start.0, start.1), at(end.0, end.1)),
None,
text.to_owned(),
)
.into()
}
#[test]
fn offsets_count_in_the_encoding_and_clamp_past_the_end() {
let text = "a😀b\r\nc\rd";
for (position, encoding, expected) in [
(at(0, 3), PositionEncodingKind::UTF16, Some(5)),
(at(0, 2), PositionEncodingKind::UTF16, None),
(at(0, 5), PositionEncodingKind::UTF8, Some(5)),
(at(0, 2), PositionEncodingKind::UTF32, Some(5)),
(at(0, 99), PositionEncodingKind::UTF16, Some(6)),
(at(2, 1), PositionEncodingKind::UTF16, Some(11)),
(at(9, 0), PositionEncodingKind::UTF16, Some(text.len())),
(
at(u32::MAX, u32::MAX),
PositionEncodingKind::UTF8,
Some(text.len()),
),
] {
assert_eq!(offset(text, position, &encoding), expected);
}
}
#[test]
fn position_and_offset_round_trip() {
for text in [
"",
"a",
"a\n",
"a\r\n",
"a\r",
"a😀b\r\nc\rd",
"😀",
"\r\nx",
"\n\nyee\n\n",
"€ abc\nline 2",
] {
let boundaries: Vec<usize> = text
.char_indices()
.map(|(index, _)| index)
.chain([text.len()])
.filter(|&index| {
!(text[..index].ends_with('\r') && text[index..].starts_with('\n'))
})
.collect();
for encoding in [
&PositionEncodingKind::UTF8,
&PositionEncodingKind::UTF16,
&PositionEncodingKind::UTF32,
] {
for &boundary in &boundaries {
let position = position(text, boundary, encoding);
assert_eq!(offset(text, position, encoding), Some(boundary));
}
}
}
}
#[test]
fn edits_apply_against_the_original_text() {
let applied = apply(
"ab\ncd",
&[edit((1, 0), (1, 2), "x"), edit((0, 0), (0, 1), "yy")],
&PositionEncodingKind::UTF16,
)
.unwrap();
assert_eq!(applied, "yyb\nx");
let applied = apply(
"abc",
&[
edit((0, 1), (0, 2), "R"),
edit((0, 1), (0, 1), "1"),
edit((0, 1), (0, 1), "2"),
],
&PositionEncodingKind::UTF16,
)
.unwrap();
assert_eq!(applied, "a12Rc");
}
#[test]
fn edits_around_a_line_break_apply() {
let applied = apply(
"\ra",
&[edit((1, 0), (1, 0), "x"), edit((1, 0), (1, 0), "\n")],
&PositionEncodingKind::UTF16,
)
.unwrap();
assert_eq!(applied, "\rx\na");
let edits = [edit((1, 0), (1, 0), "x"), edit((1, 0), (1, 0), "\n")];
let changes = changes("\ra", &edits, &PositionEncodingKind::UTF16).unwrap();
assert_eq!(
apply_changes("\ra", &changes, &PositionEncodingKind::UTF16).unwrap(),
applied
);
}
#[test]
fn overlapping_or_invalid_edits_are_rejected() {
let overlapping = [
vec![edit((0, 0), (0, 2), ""), edit((0, 1), (0, 3), "")],
vec![edit((0, 0), (0, 2), ""), edit((0, 1), (0, 1), "x")],
vec![edit((0, 0), (0, 3), ""), edit((0, 1), (0, 2), "")],
];
for edits in overlapping {
let err = apply("abc", &edits, &PositionEncodingKind::UTF16).unwrap_err();
assert!(matches!(err.kind(), ErrorKind::OverlappingEdits), "{err}");
}
let touching = [edit((0, 0), (0, 1), "x"), edit((0, 1), (0, 2), "y")];
assert_eq!(
apply("abc", &touching, &PositionEncodingKind::UTF16).unwrap(),
"xyc"
);
for range in [((0, 2), (0, 2)), ((0, 3), (0, 1))] {
let err = apply(
"a😀b",
&[edit(range.0, range.1, "")],
&PositionEncodingKind::UTF16,
)
.unwrap_err();
assert!(
matches!(err.kind(), ErrorKind::InvalidEdit { index: 0, .. }),
"{err}"
);
}
}
#[test]
fn applied_changes_replay_to_the_same_text() {
let edits = [edit((0, 9), (0, 10), "10"), edit((1, 7), (1, 7), " ")];
let text = "{\"😀\": 1,\n \"b\": 2}";
let changes = changes(text, &edits, &PositionEncodingKind::UTF8).unwrap();
assert_eq!(
apply_changes(text, &changes, &PositionEncodingKind::UTF8).unwrap(),
apply(text, &edits, &PositionEncodingKind::UTF8).unwrap()
);
}
#[test]
fn whole_and_partial_content_changes_apply_in_order() {
assert_eq!(
apply_changes("abc", &[whole("xyz")], &PositionEncodingKind::UTF16).unwrap(),
"xyz"
);
assert_eq!(
apply_changes(
"abc",
&[partial((0, 1), (0, 2), "X"), partial((0, 1), (0, 1), "Y")],
&PositionEncodingKind::UTF16,
)
.unwrap(),
"aYXc"
);
assert_eq!(
apply_changes(
"abc",
&[whole("xyz"), partial((0, 0), (0, 1), "A")],
&PositionEncodingKind::UTF16,
)
.unwrap(),
"Ayz"
);
}
}