1#[derive(Clone, Debug, Default, PartialEq, Eq)]
2pub struct LineIndex {
3 starts: Vec<usize>,
4 len: usize,
5}
6
7fn push_unique(out: &mut Vec<usize>, v: usize) {
8 if out.last() != Some(&v) {
9 out.push(v);
10 }
11}
12
13impl LineIndex {
14 pub fn from_str(text: &str) -> Self {
15 let mut starts = vec![0usize];
16 for (i, b) in text.bytes().enumerate() {
17 if b == b'\n' {
18 starts.push(i + 1);
19 }
20 }
21 Self {
22 starts,
23 len: text.len(),
24 }
25 }
26
27 pub fn apply_edit(&mut self, start: usize, deleted_len: usize, inserted: &str) {
28 debug_assert!(start <= self.len, "edit start past end");
29 let start = start.min(self.len);
30 let deleted_len = deleted_len.min(self.len - start);
31 let ins_len = inserted.len();
32 let old_len = self.len;
33 let had_start = self.starts.binary_search(&start).is_ok();
34 let old_trailing_nl = old_len > 0 && self.starts.last() == Some(&old_len);
35
36 let need = start == 0 || self.starts.binary_search(&start).is_ok();
37
38 let mut next = Vec::with_capacity(self.starts.len() + 1);
39 for &s in &self.starts {
40 if s < start {
41 next.push(s);
42 } else {
43 break;
44 }
45 }
46 if need {
47 push_unique(&mut next, start);
48 }
49 for (i, b) in inserted.bytes().enumerate() {
50 if b == b'\n' {
51 push_unique(&mut next, start + i + 1);
52 }
53 }
54 let delta = ins_len as isize - deleted_len as isize;
55 for &s in &self.starts {
56 if s >= start + deleted_len && !(deleted_len == 0 && s == start) {
57 if deleted_len > 0 && s == start + deleted_len {
58 let reopened = if !inserted.is_empty() {
59 inserted.as_bytes().last() == Some(&b'\n')
60 } else {
61 start > 0 && had_start
62 };
63 if !reopened {
64 continue;
65 }
66 }
67 push_unique(&mut next, ((s as isize) + delta) as usize);
68 }
69 }
70 let new_len = old_len - deleted_len + ins_len;
71
72 let suffix_nonempty = start + deleted_len < old_len;
73
74 let new_ends_with_nl = if suffix_nonempty {
75 old_trailing_nl
76 } else if !inserted.is_empty() {
77 inserted.as_bytes().last() == Some(&b'\n')
78 } else {
79 start > 0 && had_start
80 };
81 while new_len > 0 && next.last() == Some(&new_len) && !new_ends_with_nl {
82 next.pop();
83 }
84 self.starts = next;
85 self.len = new_len;
86 }
87
88 pub fn starts(&self) -> &[usize] {
89 &self.starts
90 }
91
92 pub fn len(&self) -> usize {
93 self.len
94 }
95
96 pub fn is_empty(&self) -> bool {
97 self.len == 0
98 }
99
100 pub fn line_count(&self) -> usize {
101 self.starts.len()
102 }
103
104 pub fn line_of(&self, offset: usize) -> usize {
105 let offset = offset.min(self.len);
106 self.starts
107 .partition_point(|&s| s <= offset)
108 .saturating_sub(1)
109 .min(self.starts.len().saturating_sub(1))
110 }
111
112 pub fn line_col(&self, offset: usize) -> (usize, usize) {
113 let line = self.line_of(offset);
114 let offset = offset.min(self.len);
115 (line, offset.saturating_sub(self.starts[line]))
116 }
117
118 pub fn line_start(&self, line: usize) -> usize {
119 let line = line.min(self.starts.len().saturating_sub(1));
120 self.starts[line]
121 }
122
123 pub fn line_range(&self, line: usize) -> (usize, usize) {
124 let line = line.min(self.starts.len().saturating_sub(1));
125 let start = self.starts[line];
126 let end = match self.starts.get(line + 1) {
127 Some(&next) => next.saturating_sub(1),
128 None => self.len,
129 };
130 (start, end.max(start))
131 }
132
133 pub fn offset_of(&self, line: usize, col_bytes: usize) -> usize {
134 let (start, end) = self.line_range(line);
135 (start + col_bytes).min(end)
136 }
137}
138
139#[cfg(test)]
140mod tests {
141 use super::*;
142
143 fn check(text: &str) {
144 let idx = LineIndex::from_str(text);
145 let mut expect = vec![0usize];
146 for (i, b) in text.bytes().enumerate() {
147 if b == b'\n' {
148 expect.push(i + 1);
149 }
150 }
151 assert_eq!(idx.starts(), expect, "from_str({text:?})");
152 assert_eq!(idx.len(), text.len());
153 }
154
155 #[test]
156 fn from_str_models() {
157 check("");
158 check("a");
159 check("a\n");
160 check("\n");
161 check("\n\n");
162 check("a\nb\nc");
163 check("a\nb\nc\n");
164 check("yellow\ngoose\nself");
165 }
166
167 #[test]
168 fn queries() {
169 let idx = LineIndex::from_str("ab\ncde\n\nf");
170 assert_eq!(idx.line_count(), 4);
171 assert_eq!(idx.line_of(0), 0);
172 assert_eq!(idx.line_of(3), 1);
173 assert_eq!(idx.line_col(4), (1, 1));
174 assert_eq!(idx.line_range(1), (3, 6));
175 assert_eq!(idx.line_range(2), (7, 7));
176 assert_eq!(idx.line_range(3), (8, 9));
177 assert_eq!(idx.offset_of(1, 99), 6);
178 assert_eq!(idx.offset_of(99, 0), 8);
179
180 assert_eq!(idx.line_of(10_000), 3);
181 assert_eq!(idx.line_col(10_000), (3, 1));
182 }
183
184 fn apply_check(initial: &str, start: usize, delete_len: usize, insert: &str) {
185 let mut ref_text = initial.to_string();
186 ref_text.replace_range(start..start + delete_len, insert);
187 let mut idx = LineIndex::from_str(initial);
188 idx.apply_edit(start, delete_len, insert);
189 let fresh = LineIndex::from_str(&ref_text);
190 assert_eq!(
191 idx,
192 fresh,
193 "edit [{start}..{}] + {insert:?} in {initial:?} -> {ref_text:?}",
194 start + delete_len,
195 );
196 }
197
198 #[test]
199 fn edits_mid_line() {
200 apply_check("hello world", 5, 0, ",");
201 apply_check("hello world", 5, 6, "");
202 apply_check("hello", 5, 0, " world");
203 apply_check("hello world", 0, 5, "bye");
204 apply_check("abc", 0, 3, "");
205 apply_check("", 0, 0, "x");
206 apply_check("", 0, 0, "");
207 }
208
209 #[test]
210 fn edits_crossing_lines() {
211 apply_check("a\nb\nc", 2, 0, "X\nY");
212 apply_check("a\nb\nc", 2, 2, "");
213 apply_check("a\nb\nc", 0, 4, "");
214 apply_check("a\nb", 2, 1, "");
215 apply_check("a\nb", 1, 2, "");
216 apply_check("ab\ncd", 2, 2, "X");
217 apply_check("ab\ncd", 3, 0, "\n");
218 apply_check("ab", 2, 0, "\n");
219 apply_check("ab\n", 3, 0, "cd\n");
220 apply_check("a\nb\n", 2, 2, "X\n");
221 apply_check("a\nb\nc\n", 4, 2, "xyz\n123\n");
222 }
223
224 #[test]
225 fn edits_unicode() {
226 apply_check("yellow\ngoose\nself", 10, 0, "!\n?");
227 apply_check("a👨👩👧b\nc", 0, 1, "");
228 apply_check("a👨👩👧b\nc", 1, 18, "");
229 apply_check("\n", 0, 1, "");
230 apply_check("\n\n", 1, 0, "x");
231 }
232
233 #[test]
234 fn deleting_trailing_newline_drops_dangling_start() {
235 apply_check("a\nb\n", 3, 1, "");
236 apply_check("a\nb\n", 0, 4, "");
237 apply_check("a\nb", 2, 1, "");
238
239 apply_check("a\nb\n", 0, 0, "X");
240 apply_check("a\nb\n", 2, 0, "X\n");
241 apply_check("a\n", 1, 0, "b");
242 }
243}