Skip to main content

continuity_buffer/
checksum.rs

1//! Incremental FNV-1a 64-bit checksum maintenance for the buffer's rope.
2//!
3//! The persisted `buffer_edits.checksum_after` column carries the FNV-1a
4//! 64-bit hash of the rope's bytes at each revision. Recovery replays the
5//! edit log and halts the first time the replayed rope's hash diverges
6//! from the stored checksum (see `continuity-persist`'s recovery path).
7//!
8//! Computing that hash by walking the entire rope on every persisted
9//! edit costs O(rope_bytes) per edit; on a ~711 KB buffer this is ~1 ms
10//! p99 — about 3 % of the keystroke budget at the time of writing, and
11//! linear in buffer size.
12//!
13//! FNV-1a's per-byte step is `state = (state ^ byte) * FNV_PRIME`. The
14//! prime is odd, so it is invertible modulo `2^64`, and a single mix
15//! step can be peeled off the tail of the running state with
16//! `state = (state * FNV_PRIME_INV) ^ byte`. We exploit this to update
17//! the running hash for an edit in O(suffix_bytes + edit_bytes) instead
18//! of O(rope_bytes): unmix the bytes after the edit point, mix in the
19//! new (and unmix the removed) bytes, then re-mix the suffix.
20//!
21//! For an append-at-the-end edit the suffix is empty and the cost is
22//! O(edit_bytes); mid-rope edits in large buffers still touch the
23//! suffix but never the prefix.
24//!
25//! A periodic full-walk verification (every `CHECKSUM_VERIFY_INTERVAL`
26//! edits or at snapshot boundary, driven by the core thread) bounds
27//! damage from any algebraic mistake to that interval and surfaces it
28//! through `event:checksum_drift`.
29
30use ropey::Rope;
31
32use continuity_text::EditOp;
33
34use crate::Error;
35
36/// FNV-1a 64-bit offset basis. Same constant used by
37/// [`continuity_persist::fnv1a_64`]; the running state for an empty
38/// rope is exactly this value.
39pub const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
40
41/// FNV-1a 64-bit prime.
42pub const FNV_PRIME: u64 = 0x0000_0001_0000_01b3;
43
44/// Multiplicative inverse of [`FNV_PRIME`] modulo `2^64`. Computed at
45/// compile time from the Newton–Raphson recurrence
46/// `x_{k+1} = x_k * (2 - a * x_k)` (mod `2^64`), which doubles the
47/// number of correct low bits each iteration; six iterations from
48/// `x_0 = 1` (correct mod 2) take us past 64 bits.
49pub 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
61/// Periodic verification cadence — the core thread runs a full-walk
62/// cross-check every this-many persisted edits per buffer (and at
63/// snapshot boundaries). Bounds drift damage to one interval.
64pub const CHECKSUM_VERIFY_INTERVAL: u32 = 1000;
65
66/// One forward FNV-1a step. Pure.
67#[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/// One inverse FNV-1a step — peels the last `byte` off the running
74/// state. Correct only when `byte` was the most recently mixed byte;
75/// to unmix a sequence, call this back-to-front. Pure.
76#[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/// Full FNV-1a hash of `rope`'s bytes. The verification-path fallback
83/// and the initial running state for newly constructed buffers both
84/// route through here.
85#[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
127/// Update `old_state` (the running FNV-1a hash of `rope_after` before
128/// `op` was applied) to the new running hash after `op` has applied
129/// to the rope. `rope_after` must be the post-apply rope;
130/// `removed_text` is the substring `op` removed (empty for
131/// `EditOp::Insert`).
132///
133/// Cost: `2 * suffix_bytes + edit_bytes`, where `suffix_bytes` is the
134/// number of bytes in the rope after the edit point. Append-at-end
135/// edits are O(edit_bytes); mid-rope edits in large buffers still walk
136/// the suffix but never the prefix.
137///
138/// # Errors
139///
140/// Returns [`Error::Text`] when the op's positions cannot be resolved
141/// against `rope_after`. The running state must not be advanced from
142/// `old_state` in that case.
143pub 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            // suffix bytes = rope_after[after..rope_len]; same bytes as
155            // were after `p` in the pre-apply rope. Unmixing the suffix
156            // from old_state rewinds the running hash to `hash(prefix)`.
157            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            // rope_after[p..rope_len] is the unchanged suffix.
167            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        // The "insert abc, then delete abc" round trip pins the
228        // algebraic property: unmixing the bytes we just mixed gets us
229        // back to bit-for-bit the same running state.
230        let rope0 = Rope::from_str("xy");
231        let state0 = full_walk_rope(&rope0);
232
233        // Apply insert "abc" at end (Position(0, 2)).
234        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        // Apply delete of "abc" at [2..5].
241        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        // The simple "mix new bytes on top of running state" approach
268        // would diverge here because the suffix is mixed against a
269        // different prior state in the new rope; this test catches that
270        // class of bug.
271        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    /// Apply `op` to ASCII `s`. Returns the new string and the removed
282    /// substring (empty for inserts). Asserts the op is well-formed
283    /// against `s` so the proptest input filter can reject otherwise.
284    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    /// One synthetic edit recipe — proptest input shape so positions
333    /// are bounded reproducibly regardless of the buffer's evolving
334    /// length. `kind ∈ {0,1,2}` selects insert/delete/replace; `start`
335    /// and `len` are byte offsets within the current string (clamped
336    /// in the test body); `text` provides any inserted bytes.
337    #[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        /// Apply a random sequence of insert / delete / replace ops to an
364        /// ASCII string and assert the incrementally-maintained running
365        /// state equals the full-walk hash of the resulting rope at every
366        /// step. Catches any algebraic mistake in
367        /// [`update_for_edit`] that diverges from `fnv1a_64(rope)`.
368        #[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}