ochrepad_core/
changeset.rs

1//! `ChangeSet`: concrete, non-overlapping edits against one document state.
2
3use serde::{Deserialize, Serialize};
4
5use crate::position::ByteOffset;
6use crate::text::Document;
7
8#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
9pub struct Edit {
10    pub start: ByteOffset,
11    pub end: ByteOffset,
12    pub text: String,
13}
14
15impl Edit {
16    pub fn new(start: ByteOffset, end: ByteOffset, text: impl Into<String>) -> Self {
17        Self {
18            start,
19            end,
20            text: text.into(),
21        }
22    }
23
24    fn is_noop(&self) -> bool {
25        self.start == self.end && self.text.is_empty()
26    }
27}
28
29/// Which side of an insertion a position at the insertion point ends up on.
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub enum Bias {
32    Before,
33    After,
34}
35
36/// Sorted, non-overlapping, non-touching edits against a document of `base_len`
37/// bytes.
38#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
39pub struct ChangeSet {
40    base_len: ByteOffset,
41    edits: Vec<Edit>,
42}
43
44impl ChangeSet {
45    /// Sorts the edits and merges touching ones (concatenating their text) and
46    /// overlapping deletions. Overlapping edits that both insert text are a
47    /// caller bug.
48    pub fn new(base_len: ByteOffset, mut edits: Vec<Edit>) -> Self {
49        edits.retain(|e| !e.is_noop());
50        edits.sort_by_key(|e| (e.start, e.end));
51        let mut out: Vec<Edit> = Vec::with_capacity(edits.len());
52        for e in edits {
53            debug_assert!(e.start <= e.end && e.end <= base_len);
54            match out.last_mut() {
55                Some(last) if e.start <= last.end => {
56                    debug_assert!(
57                        e.start == last.end || (last.text.is_empty() && e.text.is_empty()),
58                        "overlapping edits that insert text: {last:?} {e:?}"
59                    );
60                    last.end = last.end.max(e.end);
61                    last.text.push_str(&e.text);
62                }
63                _ => out.push(e),
64            }
65        }
66        Self {
67            base_len,
68            edits: out,
69        }
70    }
71
72    pub fn edits(&self) -> &[Edit] {
73        &self.edits
74    }
75
76    /// Whether this applies to `doc`: its length matches, and the edits are
77    /// in order and apart (as [`ChangeSet::new`] leaves them), inside the
78    /// text and on character boundaries. A change set read back from disk
79    /// is checked with this before it is used.
80    pub fn fits(&self, doc: &Document) -> bool {
81        let char_boundary = |p: ByteOffset| p <= doc.len() && doc.is_char_boundary(p);
82        self.base_len == doc.len()
83            && self
84                .edits
85                .iter()
86                .all(|e| e.start <= e.end && char_boundary(e.start) && char_boundary(e.end))
87            && self.edits.windows(2).all(|w| w[0].end < w[1].start)
88    }
89
90    pub fn is_empty(&self) -> bool {
91        self.edits.is_empty()
92    }
93
94    pub fn base_len(&self) -> ByteOffset {
95        self.base_len
96    }
97
98    /// The same edits against a document `by` bytes longer at its end, as
99    /// after text was appended past every edit (follow mode).
100    pub(crate) fn extend_base(&mut self, by: usize) {
101        self.base_len = ByteOffset(self.base_len.0 + by);
102    }
103
104    pub fn new_len(&self) -> ByteOffset {
105        let delta: isize = self
106            .edits
107            .iter()
108            .map(|e| e.text.len() as isize - (e.end.0 - e.start.0) as isize)
109            .sum();
110        ByteOffset((self.base_len.0 as isize + delta) as usize)
111    }
112
113    /// Applies the edits to `doc`, which must be in the base state.
114    pub fn apply(&self, doc: &mut Document) {
115        debug_assert_eq!(doc.len(), self.base_len);
116        for e in self.edits.iter().rev() {
117            doc.replace(e.start..e.end, &e.text);
118        }
119    }
120
121    /// The change set that undoes this one. `doc` must be in the base state.
122    pub fn invert(&self, doc: &Document) -> ChangeSet {
123        let mut delta: isize = 0;
124        let mut edits = Vec::with_capacity(self.edits.len());
125        for e in &self.edits {
126            let start = ByteOffset((e.start.0 as isize + delta) as usize);
127            edits.push(Edit::new(
128                start,
129                ByteOffset(start.0 + e.text.len()),
130                doc.slice(e.start..e.end),
131            ));
132            delta += e.text.len() as isize - (e.end.0 - e.start.0) as isize;
133        }
134        ChangeSet {
135            base_len: self.new_len(),
136            edits,
137        }
138    }
139
140    /// Maps a position in the base state to the new state.
141    ///
142    /// Positions inside a replaced range move to its start (`Before`) or to the
143    /// end of the replacement (`After`). A position at the start of a non-empty
144    /// replaced range stays before it and one at its end stays after it,
145    /// whatever the bias; the bias only decides ties at pure insertions and
146    /// positions strictly inside a replaced range.
147    pub fn map_position(&self, pos: ByteOffset, bias: Bias) -> ByteOffset {
148        let mut delta: isize = 0;
149        for e in &self.edits {
150            let new_start = (e.start.0 as isize + delta) as usize;
151            let new_end = new_start + e.text.len();
152            if pos < e.start {
153                break;
154            }
155            if pos <= e.end {
156                let after = if e.start == e.end {
157                    bias == Bias::After
158                } else if pos == e.start {
159                    false
160                } else if pos == e.end {
161                    true
162                } else {
163                    bias == Bias::After
164                };
165                return ByteOffset(if after { new_end } else { new_start });
166            }
167            delta += e.text.len() as isize - (e.end.0 - e.start.0) as isize;
168        }
169        ByteOffset((pos.0 as isize + delta) as usize)
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176
177    fn b(n: usize) -> ByteOffset {
178        ByteOffset(n)
179    }
180
181    #[test]
182    fn apply_and_invert() {
183        let mut doc = Document::new("hello world");
184        let cs = ChangeSet::new(
185            doc.len(),
186            vec![Edit::new(b(6), b(11), "there"), Edit::new(b(0), b(5), "hi")],
187        );
188        let inv = cs.invert(&doc);
189        cs.apply(&mut doc);
190        assert_eq!(doc.to_string(), "hi there");
191        assert_eq!(cs.new_len(), doc.len());
192        inv.apply(&mut doc);
193        assert_eq!(doc.to_string(), "hello world");
194    }
195
196    #[test]
197    fn merges_touching_and_overlapping_deletes() {
198        let cs = ChangeSet::new(
199            b(10),
200            vec![
201                Edit::new(b(2), b(3), ""),
202                Edit::new(b(3), b(4), ""),
203                Edit::new(b(3), b(5), ""),
204                Edit::new(b(7), b(7), ""),
205            ],
206        );
207        assert_eq!(cs.edits(), &[Edit::new(b(2), b(5), "")]);
208    }
209
210    #[test]
211    fn map_position_bias() {
212        // Insert "XY" at 2, replace 5..7 with "Z".
213        let cs = ChangeSet::new(
214            b(10),
215            vec![Edit::new(b(2), b(2), "XY"), Edit::new(b(5), b(7), "Z")],
216        );
217        let m = |p, bias| cs.map_position(b(p), bias).0;
218        assert_eq!(m(1, Bias::After), 1);
219        assert_eq!(m(2, Bias::Before), 2);
220        assert_eq!(m(2, Bias::After), 4);
221        assert_eq!(m(4, Bias::Before), 6);
222        assert_eq!(m(5, Bias::After), 7); // start of replaced range stays before
223        assert_eq!(m(6, Bias::Before), 7);
224        assert_eq!(m(6, Bias::After), 8);
225        assert_eq!(m(7, Bias::Before), 8); // end of replaced range stays after
226        assert_eq!(m(10, Bias::Before), 11);
227    }
228}
ochrepad_core/changeset.rs

ochrepad_core/
changeset.rs
