strop_core/history/
validate.rs

1//! Validation at the untrusted persistence boundary, using shared rope snapshots.
2use super::{Edit, EditKind, History};
3use ropey::Rope;
4
5#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
6pub enum HistoryError {
7    #[error("invalid history revision graph")]
8    Graph,
9    #[error("history edit range is outside text or splits UTF-8")]
10    Range,
11    #[error("history edit does not match the recorded text")]
12    TextMismatch,
13}
14
15impl History {
16    pub fn validate(&self) -> Result<(), HistoryError> {
17        if self.revisions.is_empty() || self.current >= self.revisions.len() {
18            return Err(HistoryError::Graph);
19        }
20        for (index, revision) in self.revisions.iter().enumerate() {
21            if (index == 0 && revision.parent != 0) || (index > 0 && revision.parent >= index) {
22                return Err(HistoryError::Graph);
23            }
24            if let Some(child) = revision.last_child {
25                if child <= index
26                    || child >= self.revisions.len()
27                    || self.revisions[child].parent != index
28                {
29                    return Err(HistoryError::Graph);
30                }
31            }
32        }
33        Ok(())
34    }
35
36    pub fn validate_for(&self, text: &Rope) -> Result<(), HistoryError> {
37        self.validate()?;
38        if self.pending.is_some() {
39            return Err(HistoryError::Graph);
40        }
41        let mut root = text.clone();
42        let mut current = self.current;
43        while current != 0 {
44            apply(&mut root, self.revisions[current].undo.iter().rev())?;
45            current = self.revisions[current].parent;
46        }
47        let mut states = Vec::with_capacity(self.revisions.len());
48        states.push(root);
49        for revision in self.revisions.iter().skip(1) {
50            let parent = &states[revision.parent];
51            let mut child = parent.clone();
52            apply(&mut child, revision.redo.iter())?;
53            let mut restored = child.clone();
54            apply(&mut restored, revision.undo.iter().rev())?;
55            if &restored != parent {
56                return Err(HistoryError::TextMismatch);
57            }
58            states.push(child);
59        }
60        if states[self.current] != *text {
61            return Err(HistoryError::TextMismatch);
62        }
63        Ok(())
64    }
65}
66
67fn boundary(text: &Rope, byte: usize) -> bool {
68    byte <= text.len_bytes() && text.char_to_byte(text.byte_to_char(byte)) == byte
69}
70
71fn apply<'a>(text: &mut Rope, edits: impl Iterator<Item = &'a Edit>) -> Result<(), HistoryError> {
72    for edit in edits {
73        if !boundary(text, edit.at) {
74            return Err(HistoryError::Range);
75        }
76        match edit.kind {
77            EditKind::Insert => text.insert(text.byte_to_char(edit.at), &edit.text),
78            EditKind::Delete => {
79                let end = edit
80                    .at
81                    .checked_add(edit.text.len())
82                    .ok_or(HistoryError::Range)?;
83                if !boundary(text, end) {
84                    return Err(HistoryError::Range);
85                }
86                if text.byte_slice(edit.at..end) != edit.text {
87                    return Err(HistoryError::TextMismatch);
88                }
89                text.remove(text.byte_to_char(edit.at)..text.byte_to_char(end));
90            }
91        }
92    }
93    Ok(())
94}
strop_core/history/validate.rs

strop_core/history/
validate.rs
