taino_edit_core/
map.rs

1//! Position mapping: [`StepMap`] (how one step moves positions) and
2//! [`Mapping`] (a composable, mirror-aware pipeline of them).
3//!
4//! Faithful port of ProseMirror's `map.ts`. The mirror/recover machinery is
5//! what lets a position survive being mapped through a step and later its
6//! inverse (undo/redo) instead of collapsing into a deleted range.
7
8const LOWER16: u64 = 0xffff;
9const FACTOR16: u64 = 1 << 16;
10
11fn make_recover(index: usize, offset: usize) -> u64 {
12    index as u64 + (offset as u64) * FACTOR16
13}
14fn recover_index(value: u64) -> usize {
15    (value & LOWER16) as usize
16}
17fn recover_offset(value: u64) -> usize {
18    ((value - (value & LOWER16)) / FACTOR16) as usize
19}
20
21/// Position was deleted on the side the association pointed at.
22pub const DEL_SIDE: u8 = 8;
23const DEL_BEFORE: u8 = 1;
24const DEL_AFTER: u8 = 2;
25const DEL_ACROSS: u8 = 4;
26
27/// The result of mapping a single position: the new position plus
28/// information about whether the content around it was deleted.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub struct MapResult {
31    /// The mapped position.
32    pub pos: usize,
33    del_info: u8,
34    recover: Option<u64>,
35}
36
37impl MapResult {
38    /// Whether the position itself fell inside deleted content (on the
39    /// associated side).
40    pub fn deleted(&self) -> bool {
41        self.del_info & DEL_SIDE > 0
42    }
43    /// Whether content directly before the position was deleted.
44    pub fn deleted_before(&self) -> bool {
45        self.del_info & (DEL_BEFORE | DEL_ACROSS) > 0
46    }
47    /// Whether content directly after the position was deleted.
48    pub fn deleted_after(&self) -> bool {
49        self.del_info & (DEL_AFTER | DEL_ACROSS) > 0
50    }
51    /// Whether the position sat strictly inside deleted content.
52    pub fn deleted_across(&self) -> bool {
53        self.del_info & DEL_ACROSS > 0
54    }
55}
56
57/// How one step remaps positions. `ranges` is a flat list of
58/// `(start, old_size, new_size)` triples.
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct StepMap {
61    ranges: Vec<usize>,
62    inverted: bool,
63}
64
65impl StepMap {
66    /// A map from `(start, old_size, new_size)` triples.
67    pub fn new(ranges: Vec<usize>) -> Self {
68        debug_assert!(ranges.len() % 3 == 0);
69        StepMap {
70            ranges,
71            inverted: false,
72        }
73    }
74
75    /// The identity map (no position changes).
76    pub fn identity() -> Self {
77        StepMap {
78            ranges: Vec::new(),
79            inverted: false,
80        }
81    }
82
83    /// The inverse of this map (swaps old/new sizes).
84    pub fn invert(&self) -> StepMap {
85        StepMap {
86            ranges: self.ranges.clone(),
87            inverted: !self.inverted,
88        }
89    }
90
91    fn recover(&self, value: u64) -> usize {
92        let mut diff: i64 = 0;
93        let index = recover_index(value);
94        if !self.inverted {
95            for i in 0..index {
96                diff += self.ranges[i * 3 + 2] as i64 - self.ranges[i * 3 + 1] as i64;
97            }
98        }
99        (self.ranges[index * 3] as i64 + diff + recover_offset(value) as i64) as usize
100    }
101
102    /// Map `pos` to its new location (association `assoc`: `-1` biases toward
103    /// content before the position, `1` toward content after).
104    pub fn map(&self, pos: usize, assoc: i32) -> usize {
105        self.map_inner(pos, assoc).pos
106    }
107
108    /// Like [`map`](StepMap::map) but also reports deletion around `pos`.
109    pub fn map_result(&self, pos: usize, assoc: i32) -> MapResult {
110        self.map_inner(pos, assoc)
111    }
112
113    fn map_inner(&self, pos: usize, assoc: i32) -> MapResult {
114        let mut diff: i64 = 0;
115        let mut i = 0;
116        while i < self.ranges.len() {
117            let start_raw = self.ranges[i] as i64 - if self.inverted { diff } else { 0 };
118            if start_raw > pos as i64 {
119                break;
120            }
121            let start = start_raw as usize;
122            let old_size = self.ranges[i + if self.inverted { 2 } else { 1 }];
123            let new_size = self.ranges[i + if self.inverted { 1 } else { 2 }];
124            let end = start + old_size;
125            if pos <= end {
126                let side = if old_size == 0 {
127                    assoc
128                } else if pos == start {
129                    -1
130                } else if pos == end {
131                    1
132                } else {
133                    assoc
134                };
135                let result =
136                    (start as i64 + diff + if side < 0 { 0 } else { new_size as i64 }) as usize;
137                let edge = if assoc < 0 { start } else { end };
138                let recover = if pos == edge {
139                    None
140                } else {
141                    Some(make_recover(i / 3, pos - start))
142                };
143                let mut del_info = if pos == start {
144                    DEL_AFTER
145                } else if pos == end {
146                    DEL_BEFORE
147                } else {
148                    DEL_ACROSS
149                };
150                let on_edge = if assoc < 0 { pos != start } else { pos != end };
151                if on_edge {
152                    del_info |= DEL_SIDE;
153                }
154                return MapResult {
155                    pos: result,
156                    del_info,
157                    recover,
158                };
159            }
160            diff += new_size as i64 - old_size as i64;
161            i += 3;
162        }
163        MapResult {
164            pos: (pos as i64 + diff) as usize,
165            del_info: 0,
166            recover: None,
167        }
168    }
169}
170
171/// A composable pipeline of [`StepMap`]s, with optional mirror links so a
172/// position can be recovered when mapped through a map and its mirror.
173#[derive(Debug, Clone, Default)]
174pub struct Mapping {
175    maps: Vec<StepMap>,
176    /// Flat pairs `[a, b, ...]` linking mirrored map indices.
177    mirror: Vec<usize>,
178}
179
180impl Mapping {
181    /// An empty mapping.
182    pub fn new() -> Self {
183        Mapping::default()
184    }
185
186    /// Number of maps in the pipeline.
187    pub fn len(&self) -> usize {
188        self.maps.len()
189    }
190
191    /// Whether the pipeline is empty.
192    pub fn is_empty(&self) -> bool {
193        self.maps.is_empty()
194    }
195
196    /// The maps, in order.
197    pub fn maps(&self) -> &[StepMap] {
198        &self.maps
199    }
200
201    /// Append a map to the pipeline.
202    pub fn append_map(&mut self, map: StepMap) {
203        self.maps.push(map);
204    }
205
206    /// Append `map`, mirrored against the existing map at index `mirrors`.
207    pub fn append_map_mirrored(&mut self, map: StepMap, mirrors: usize) {
208        self.maps.push(map);
209        let n = self.maps.len() - 1;
210        self.mirror.push(mirrors);
211        self.mirror.push(n);
212    }
213
214    fn get_mirror(&self, n: usize) -> Option<usize> {
215        let mut i = 0;
216        while i < self.mirror.len() {
217            if self.mirror[i] == n {
218                return Some(self.mirror[i + 1]);
219            }
220            if self.mirror[i + 1] == n {
221                return Some(self.mirror[i]);
222            }
223            i += 2;
224        }
225        None
226    }
227
228    /// Map `pos` through the whole pipeline.
229    pub fn map(&self, pos: usize, assoc: i32) -> usize {
230        let mut pos = pos;
231        let mut i = 0;
232        while i < self.maps.len() {
233            pos = self.maps[i].map(pos, assoc);
234            i += 1;
235        }
236        pos
237    }
238
239    /// Map `pos`, skipping across mirrored map pairs via recovery so a
240    /// position survives a step followed by its inverse.
241    pub fn map_result(&self, pos: usize, assoc: i32) -> MapResult {
242        let mut del_info = 0u8;
243        let mut pos = pos;
244        let mut i = 0;
245        while i < self.maps.len() {
246            let result = self.maps[i].map_result(pos, assoc);
247            if let Some(rec) = result.recover {
248                if let Some(corr) = self.get_mirror(i) {
249                    if corr > i && corr < self.maps.len() {
250                        i = corr;
251                        pos = self.maps[corr].recover(rec);
252                        i += 1;
253                        continue;
254                    }
255                }
256            }
257            del_info |= result.del_info;
258            pos = result.pos;
259            i += 1;
260        }
261        MapResult {
262            pos,
263            del_info,
264            recover: None,
265        }
266    }
267}
taino_edit_core/map.rs

taino_edit_core/
map.rs
