ochrepad_core/
changeset.rs

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

ochrepad_core/
changeset.rs
