1use ropey::Rope;
31
32use continuity_text::EditOp;
33
34use crate::Error;
35
36pub const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
40
41pub const FNV_PRIME: u64 = 0x0000_0001_0000_01b3;
43
44pub const FNV_PRIME_INV: u64 = compute_modular_inverse_pow2(FNV_PRIME);
50
51const fn compute_modular_inverse_pow2(a: u64) -> u64 {
52 let mut x: u64 = 1;
53 let mut i = 0;
54 while i < 6 {
55 x = x.wrapping_mul(2u64.wrapping_sub(a.wrapping_mul(x)));
56 i += 1;
57 }
58 x
59}
60
61pub const CHECKSUM_VERIFY_INTERVAL: u32 = 1000;
65
66#[inline]
68#[must_use]
69pub fn mix_byte(state: u64, byte: u8) -> u64 {
70 (state ^ u64::from(byte)).wrapping_mul(FNV_PRIME)
71}
72
73#[inline]
77#[must_use]
78pub fn unmix_byte(state: u64, byte: u8) -> u64 {
79 state.wrapping_mul(FNV_PRIME_INV) ^ u64::from(byte)
80}
81
82#[must_use]
86pub fn full_walk_rope(rope: &Rope) -> u64 {
87 let mut state = FNV_OFFSET_BASIS;
88 for chunk in rope.chunks() {
89 for &b in chunk.as_bytes() {
90 state = mix_byte(state, b);
91 }
92 }
93 state
94}
95
96fn mix_rope_range(state: u64, rope: &Rope, start: usize, end: usize) -> u64 {
97 let mut s = state;
98 let slice = rope.byte_slice(start..end);
99 for chunk in slice.chunks() {
100 for &b in chunk.as_bytes() {
101 s = mix_byte(s, b);
102 }
103 }
104 s
105}
106
107fn unmix_rope_range_reverse(state: u64, rope: &Rope, start: usize, end: usize) -> u64 {
108 let mut s = state;
109 let slice = rope.byte_slice(start..end);
110 let chunks: Vec<_> = slice.chunks().collect();
111 for chunk in chunks.into_iter().rev() {
112 for &b in chunk.as_bytes().iter().rev() {
113 s = unmix_byte(s, b);
114 }
115 }
116 s
117}
118
119fn unmix_bytes_reverse(state: u64, bytes: &[u8]) -> u64 {
120 let mut s = state;
121 for &b in bytes.iter().rev() {
122 s = unmix_byte(s, b);
123 }
124 s
125}
126
127pub fn update_for_edit(
144 old_state: u64,
145 rope_after: &Rope,
146 op: &EditOp,
147 removed_text: &str,
148) -> Result<u64, Error> {
149 let rope_len = rope_after.len_bytes();
150 match op {
151 EditOp::Insert { at, text } => {
152 let p = at.to_byte_offset(rope_after)?;
153 let after = p.saturating_add(text.len()).min(rope_len);
154 let mut s = unmix_rope_range_reverse(old_state, rope_after, after, rope_len);
158 for &b in text.as_bytes() {
159 s = mix_byte(s, b);
160 }
161 s = mix_rope_range(s, rope_after, after, rope_len);
162 Ok(s)
163 }
164 EditOp::Delete { range } => {
165 let p = range.start.to_byte_offset(rope_after)?;
166 let mut s = unmix_rope_range_reverse(old_state, rope_after, p, rope_len);
168 s = unmix_bytes_reverse(s, removed_text.as_bytes());
169 s = mix_rope_range(s, rope_after, p, rope_len);
170 Ok(s)
171 }
172 EditOp::Replace { range, text } => {
173 let p = range.start.to_byte_offset(rope_after)?;
174 let after = p.saturating_add(text.len()).min(rope_len);
175 let mut s = unmix_rope_range_reverse(old_state, rope_after, after, rope_len);
176 s = unmix_bytes_reverse(s, removed_text.as_bytes());
177 for &b in text.as_bytes() {
178 s = mix_byte(s, b);
179 }
180 s = mix_rope_range(s, rope_after, after, rope_len);
181 Ok(s)
182 }
183 }
184}
185
186#[cfg(test)]
187mod tests {
188 use super::*;
189 use continuity_text::{Position, Range};
190 use proptest::prelude::*;
191
192 fn fnv_bytes(bytes: &[u8]) -> u64 {
193 let mut s = FNV_OFFSET_BASIS;
194 for &b in bytes {
195 s = mix_byte(s, b);
196 }
197 s
198 }
199
200 #[test]
201 fn prime_and_inverse_multiply_to_one() {
202 assert_eq!(FNV_PRIME.wrapping_mul(FNV_PRIME_INV), 1);
203 }
204
205 #[test]
206 fn full_walk_empty_rope_is_offset_basis() {
207 let rope = Rope::new();
208 assert_eq!(full_walk_rope(&rope), FNV_OFFSET_BASIS);
209 }
210
211 #[test]
212 fn full_walk_matches_byte_walk() {
213 let s = "hello world\nlorem ipsum dolor";
214 let rope = Rope::from_str(s);
215 assert_eq!(full_walk_rope(&rope), fnv_bytes(s.as_bytes()));
216 }
217
218 #[test]
219 fn mix_then_unmix_round_trips_one_byte() {
220 let s = 0xdead_beef_1234_5678u64;
221 let s2 = mix_byte(s, b'q');
222 assert_eq!(unmix_byte(s2, b'q'), s);
223 }
224
225 #[test]
226 fn insert_then_delete_returns_running_state() {
227 let rope0 = Rope::from_str("xy");
231 let state0 = full_walk_rope(&rope0);
232
233 let mut rope1 = rope0.clone();
235 rope1.insert(rope1.byte_to_char(2), "abc");
236 let op_insert = EditOp::insert(Position::new(0, 2), "abc".to_string());
237 let state1 = update_for_edit(state0, &rope1, &op_insert, "").unwrap();
238 assert_eq!(state1, full_walk_rope(&rope1));
239
240 let mut rope2 = rope1.clone();
242 rope2.remove(rope2.byte_to_char(2)..rope2.byte_to_char(5));
243 let op_delete = EditOp::delete(Range::new(Position::new(0, 2), Position::new(0, 5)));
244 let state2 = update_for_edit(state1, &rope2, &op_delete, "abc").unwrap();
245 assert_eq!(state2, state0);
246 assert_eq!(state2, full_walk_rope(&rope2));
247 }
248
249 #[test]
250 fn replace_matches_full_walk() {
251 let rope0 = Rope::from_str("hello world");
252 let state0 = full_walk_rope(&rope0);
253 let mut rope1 = rope0.clone();
254 rope1.remove(rope1.byte_to_char(6)..rope1.byte_to_char(11));
255 rope1.insert(rope1.byte_to_char(6), "rust");
256 assert_eq!(rope1.to_string(), "hello rust");
257 let op = EditOp::replace(
258 Range::new(Position::new(0, 6), Position::new(0, 11)),
259 "rust".to_string(),
260 );
261 let state1 = update_for_edit(state0, &rope1, &op, "world").unwrap();
262 assert_eq!(state1, full_walk_rope(&rope1));
263 }
264
265 #[test]
266 fn mid_rope_insert_matches_full_walk() {
267 let rope0 = Rope::from_str("abcdefghij");
272 let state0 = full_walk_rope(&rope0);
273 let mut rope1 = rope0.clone();
274 rope1.insert(rope1.byte_to_char(3), "XYZ");
275 assert_eq!(rope1.to_string(), "abcXYZdefghij");
276 let op = EditOp::insert(Position::new(0, 3), "XYZ".to_string());
277 let state1 = update_for_edit(state0, &rope1, &op, "").unwrap();
278 assert_eq!(state1, full_walk_rope(&rope1));
279 }
280
281 fn apply_edit_op_to_ascii(s: &str, op: &EditOp) -> Option<(String, String)> {
285 match op {
286 EditOp::Insert { at, text } => {
287 if at.line != 0 {
288 return None;
289 }
290 let b = at.byte_in_line as usize;
291 if b > s.len() {
292 return None;
293 }
294 let mut out = String::with_capacity(s.len() + text.len());
295 out.push_str(&s[..b]);
296 out.push_str(text);
297 out.push_str(&s[b..]);
298 Some((out, String::new()))
299 }
300 EditOp::Delete { range } => {
301 if range.start.line != 0 || range.end.line != 0 {
302 return None;
303 }
304 let lo = range.start.byte_in_line as usize;
305 let hi = range.end.byte_in_line as usize;
306 if lo > hi || hi > s.len() {
307 return None;
308 }
309 let mut out = String::with_capacity(s.len() - (hi - lo));
310 out.push_str(&s[..lo]);
311 out.push_str(&s[hi..]);
312 Some((out, s[lo..hi].to_string()))
313 }
314 EditOp::Replace { range, text } => {
315 if range.start.line != 0 || range.end.line != 0 {
316 return None;
317 }
318 let lo = range.start.byte_in_line as usize;
319 let hi = range.end.byte_in_line as usize;
320 if lo > hi || hi > s.len() {
321 return None;
322 }
323 let mut out = String::with_capacity(s.len() + text.len());
324 out.push_str(&s[..lo]);
325 out.push_str(text);
326 out.push_str(&s[hi..]);
327 Some((out, s[lo..hi].to_string()))
328 }
329 }
330 }
331
332 #[derive(Clone, Debug)]
338 struct EditRecipe {
339 kind: u8,
340 start: u8,
341 len: u8,
342 text: String,
343 }
344
345 fn arb_recipe() -> impl Strategy<Value = EditRecipe> {
346 (
347 0u8..3,
348 any::<u8>(),
349 any::<u8>(),
350 proptest::collection::vec(b'a'..=b'z', 0..=8),
351 )
352 .prop_map(|(k, s, l, bytes)| EditRecipe {
353 kind: k,
354 start: s,
355 len: l,
356 text: String::from_utf8(bytes).expect("invariant: ASCII bytes are valid UTF-8"),
357 })
358 }
359
360 proptest! {
361 #![proptest_config(ProptestConfig::with_cases(48))]
362
363 #[test]
369 fn random_op_sequence_running_state_tracks_full_walk(
370 initial in "[a-zA-Z0-9 ]{0,32}",
371 recipes in proptest::collection::vec(arb_recipe(), 1..=10),
372 ) {
373 let mut s = initial;
374 let mut state = full_walk_rope(&Rope::from_str(&s));
375 prop_assert_eq!(state, fnv_bytes(s.as_bytes()));
376
377 for recipe in recipes {
378 let p = if s.is_empty() {
379 0
380 } else {
381 (recipe.start as usize) % (s.len() + 1)
382 };
383 let q = p.saturating_add((recipe.len as usize) % (s.len() - p + 1));
384 let p_u32 = p as u32;
385 let q_u32 = q as u32;
386 let op = match recipe.kind % 3 {
387 0 => EditOp::insert(Position::new(0, p_u32), recipe.text.clone()),
388 1 => EditOp::delete(Range::new(
389 Position::new(0, p_u32),
390 Position::new(0, q_u32),
391 )),
392 _ => EditOp::replace(
393 Range::new(Position::new(0, p_u32), Position::new(0, q_u32)),
394 recipe.text.clone(),
395 ),
396 };
397
398 let Some((after, removed)) = apply_edit_op_to_ascii(&s, &op) else {
399 continue;
400 };
401 let rope_after = Rope::from_str(&after);
402 state = update_for_edit(state, &rope_after, &op, &removed).unwrap();
403 prop_assert_eq!(state, full_walk_rope(&rope_after));
404 prop_assert_eq!(state, fnv_bytes(after.as_bytes()));
405 s = after;
406 }
407 }
408 }
409}