taino_edit_core/
replace.rs

1//! The tree-replace algorithm: substitute the document range `from..to`
2//! with a [`Slice`], producing a new, schema-valid document.
3//!
4//! This is a faithful port of ProseMirror's `replace.ts` (the most subtle
5//! piece of the model). It is purely functional — nodes are immutable, so
6//! `replace` returns a fresh root and the old tree is untouched, which is
7//! exactly what invertible [`Step`](crate::Step)s and undo/redo need.
8
9use std::fmt;
10
11use crate::error::DocError;
12use crate::fragment::Fragment;
13use crate::node::Node;
14use crate::pos::ResolvedPos;
15use crate::schema::Schema;
16use crate::slice::Slice;
17
18/// Why a [`Node::replace`] could not be performed.
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub enum ReplaceError {
21    /// The slice's open depth exceeds the insertion position's depth.
22    OpenTooDeep,
23    /// `from`'s and `to`'s open depths are inconsistent with the slice.
24    InconsistentOpenDepths,
25    /// Two nodes that would have to be joined have incompatible content.
26    CannotJoin {
27        /// The node type being joined on.
28        onto: String,
29        /// The node type being joined.
30        joined: String,
31    },
32    /// The resulting content would violate the schema for `parent`.
33    InvalidContent {
34        /// The parent node type whose content became invalid.
35        parent: String,
36    },
37    /// A boundary position was out of range.
38    Position {
39        /// The offending position.
40        pos: usize,
41        /// The maximum valid position.
42        max: usize,
43    },
44}
45
46impl fmt::Display for ReplaceError {
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        match self {
49            ReplaceError::OpenTooDeep => {
50                write!(f, "inserted content deeper than the insertion position")
51            }
52            ReplaceError::InconsistentOpenDepths => write!(f, "inconsistent open depths"),
53            ReplaceError::CannotJoin { onto, joined } => {
54                write!(f, "cannot join `{joined}` onto `{onto}`")
55            }
56            ReplaceError::InvalidContent { parent } => {
57                write!(f, "replacement violates the schema for `{parent}`")
58            }
59            ReplaceError::Position { pos, max } => {
60                write!(f, "position {pos} out of range (max {max})")
61            }
62        }
63    }
64}
65
66impl std::error::Error for ReplaceError {}
67
68fn map_pos(e: DocError) -> ReplaceError {
69    match e {
70        DocError::PositionOutOfRange { pos, max } => ReplaceError::Position { pos, max },
71        _ => ReplaceError::Position { pos: 0, max: 0 },
72    }
73}
74
75impl Node {
76    /// Replace the range `from..to` with `slice`, returning the new root.
77    ///
78    /// The document is treated as the root. Content that would violate the
79    /// schema (including illegal joins at the boundaries) is rejected with a
80    /// [`ReplaceError`] rather than silently produced.
81    pub fn replace(
82        &self,
83        from: usize,
84        to: usize,
85        slice: &Slice,
86        schema: &Schema,
87    ) -> Result<Node, ReplaceError> {
88        let rf = ResolvedPos::resolve(self, from).map_err(map_pos)?;
89        let rt = ResolvedPos::resolve(self, to).map_err(map_pos)?;
90        replace(&rf, &rt, slice, schema)
91    }
92
93    /// Extract the content between `from` and `to` as a [`Slice`], recording
94    /// how deeply each end is open so it can be re-inserted faithfully.
95    pub fn slice(&self, from: usize, to: usize) -> Result<Slice, DocError> {
96        if from == to {
97            return Ok(Slice::empty());
98        }
99        let rf = ResolvedPos::resolve(self, from)?;
100        let rt = ResolvedPos::resolve(self, to)?;
101        let depth = rf.shared_depth(to);
102        let start = rf.start(depth);
103        let node = rf.node(depth);
104        let content = node.content().cut(rf.pos() - start, rt.pos() - start);
105        Ok(Slice::new(content, rf.depth() - depth, rt.depth() - depth))
106    }
107}
108
109fn replace(
110    from: &ResolvedPos,
111    to: &ResolvedPos,
112    slice: &Slice,
113    schema: &Schema,
114) -> Result<Node, ReplaceError> {
115    if slice.open_start() > from.depth() {
116        return Err(ReplaceError::OpenTooDeep);
117    }
118    if from.depth() as isize - slice.open_start() as isize
119        != to.depth() as isize - slice.open_end() as isize
120    {
121        return Err(ReplaceError::InconsistentOpenDepths);
122    }
123    replace_outer(from, to, slice, 0, schema)
124}
125
126fn close(schema: &Schema, template: &Node, content: Fragment) -> Result<Node, ReplaceError> {
127    if !schema.fragment_valid(template.node_type(), &content) {
128        return Err(ReplaceError::InvalidContent {
129            parent: template.node_type().name().to_string(),
130        });
131    }
132    Ok(template.copy_content(content))
133}
134
135/// Validate that a node of type `joined` can be joined onto `onto`.
136fn check_join(schema: &Schema, onto: &Node, joined: &Node) -> Result<(), ReplaceError> {
137    if !schema.types_compatible(joined.node_type(), onto.node_type()) {
138        return Err(ReplaceError::CannotJoin {
139            onto: onto.node_type().name().to_string(),
140            joined: joined.node_type().name().to_string(),
141        });
142    }
143    Ok(())
144}
145
146fn joinable(
147    schema: &Schema,
148    before: &ResolvedPos,
149    after: &ResolvedPos,
150    depth: usize,
151) -> Result<Node, ReplaceError> {
152    let node = before.node(depth).clone();
153    check_join(schema, &node, after.node(depth))?;
154    Ok(node)
155}
156
157fn add_node(child: Node, target: &mut Vec<Node>) {
158    if let Some(last) = target.last() {
159        if child.is_text() && last.is_text() && child.same_markup(last) {
160            let merged = child.with_text(format!(
161                "{}{}",
162                last.text().unwrap_or(""),
163                child.text().unwrap_or("")
164            ));
165            let n = target.len() - 1;
166            target[n] = merged;
167            return;
168        }
169    }
170    target.push(child);
171}
172
173fn add_range(
174    start: Option<&ResolvedPos>,
175    end: Option<&ResolvedPos>,
176    depth: usize,
177    target: &mut Vec<Node>,
178) {
179    let anchor = end.or(start).expect("add_range needs a bound");
180    let node = anchor.node(depth);
181    let mut start_index = 0;
182    let end_index = match end {
183        Some(e) => e.index(depth),
184        None => node.child_count(),
185    };
186    if let Some(s) = start {
187        start_index = s.index(depth);
188        if s.depth() > depth {
189            start_index += 1;
190        } else if s.text_offset() > 0 {
191            add_node(s.node_after().expect("node after start"), target);
192            start_index += 1;
193        }
194    }
195    for i in start_index..end_index {
196        add_node(node.child(i).clone(), target);
197    }
198    if let Some(e) = end {
199        if e.depth() == depth && e.text_offset() > 0 {
200            add_node(e.node_before().expect("node before end"), target);
201        }
202    }
203}
204
205fn replace_two_way(
206    from: &ResolvedPos,
207    to: &ResolvedPos,
208    depth: usize,
209    schema: &Schema,
210) -> Result<Fragment, ReplaceError> {
211    let mut content = Vec::new();
212    add_range(None, Some(from), depth, &mut content);
213    if from.depth() > depth {
214        let template = joinable(schema, from, to, depth + 1)?;
215        let inner = replace_two_way(from, to, depth + 1, schema)?;
216        add_node(close(schema, &template, inner)?, &mut content);
217    }
218    add_range(Some(to), None, depth, &mut content);
219    Ok(Fragment::from_vec(content))
220}
221
222#[allow(clippy::too_many_arguments)]
223fn replace_three_way(
224    from: &ResolvedPos,
225    start: &ResolvedPos,
226    end: &ResolvedPos,
227    to: &ResolvedPos,
228    depth: usize,
229    schema: &Schema,
230) -> Result<Fragment, ReplaceError> {
231    let open_start = if from.depth() > depth {
232        Some(joinable(schema, from, start, depth + 1)?)
233    } else {
234        None
235    };
236    let open_end = if to.depth() > depth {
237        Some(joinable(schema, end, to, depth + 1)?)
238    } else {
239        None
240    };
241
242    let mut content = Vec::new();
243    add_range(None, Some(from), depth, &mut content);
244
245    match (&open_start, &open_end) {
246        (Some(os), Some(oe)) if start.index(depth) == end.index(depth) => {
247            check_join(schema, os, oe)?;
248            let inner = replace_three_way(from, start, end, to, depth + 1, schema)?;
249            add_node(close(schema, os, inner)?, &mut content);
250        }
251        _ => {
252            if let Some(os) = &open_start {
253                let inner = replace_two_way(from, start, depth + 1, schema)?;
254                add_node(close(schema, os, inner)?, &mut content);
255            }
256            add_range(Some(start), Some(end), depth, &mut content);
257            if let Some(oe) = &open_end {
258                let inner = replace_two_way(end, to, depth + 1, schema)?;
259                add_node(close(schema, oe, inner)?, &mut content);
260            }
261        }
262    }
263
264    add_range(Some(to), None, depth, &mut content);
265    Ok(Fragment::from_vec(content))
266}
267
268fn prepare_slice_for_replace(
269    slice: &Slice,
270    along: &ResolvedPos,
271) -> Result<(Node, ResolvedPos, ResolvedPos), DocError> {
272    let extra = along.depth() - slice.open_start();
273    let parent = along.node(extra);
274    let mut node = parent.copy_content(slice.content().clone());
275    for i in (0..extra).rev() {
276        node = along.node(i).copy_content(Fragment::from_vec(vec![node]));
277    }
278    let start = ResolvedPos::resolve(&node, slice.open_start() + extra)?;
279    let end_pos = node.content().size() - slice.open_end() - extra;
280    let end = ResolvedPos::resolve(&node, end_pos)?;
281    Ok((node, start, end))
282}
283
284fn replace_outer(
285    from: &ResolvedPos,
286    to: &ResolvedPos,
287    slice: &Slice,
288    depth: usize,
289    schema: &Schema,
290) -> Result<Node, ReplaceError> {
291    let index = from.index(depth);
292    let node = from.node(depth).clone();
293    if index == to.index(depth) && depth < from.depth() - slice.open_start() {
294        let inner = replace_outer(from, to, slice, depth + 1, schema)?;
295        Ok(node.copy_content(node.content().replace_child(index, inner)))
296    } else if slice.content().size() == 0 {
297        let frag = replace_two_way(from, to, depth, schema)?;
298        close(schema, &node, frag)
299    } else if slice.open_start() == 0
300        && slice.open_end() == 0
301        && from.depth() == depth
302        && to.depth() == depth
303    {
304        let parent = from.parent().clone();
305        let content = parent.content();
306        let merged = content
307            .cut(0, from.parent_offset())
308            .append(slice.content())
309            .append(&content.cut(to.parent_offset(), content.size()));
310        close(schema, &parent, merged)
311    } else {
312        let (_root, start, end) = prepare_slice_for_replace(slice, from).map_err(map_pos)?;
313        let frag = replace_three_way(from, &start, &end, to, depth, schema)?;
314        close(schema, &node, frag)
315    }
316}
taino_edit_core/replace.rs

taino_edit_core/
replace.rs
