tiptap_rusty_parser/change_ops.rs
1//! Utilities over [`Change`] lists: compose, compact, and position mapping.
2//!
3//! These complement [`diff`](crate::diff)/[`apply`](crate::apply)/[`invert`](crate::invert):
4//! - [`compose`] concatenates two change lists into one apply-equivalent patch.
5//! - [`compact`] coalesces redundant node-local ops (safely — structural ops act
6//! as barriers, since [`apply`] interprets child indices against the live tree).
7//! - [`map_path`] carries an index-path through a change list (the basis for
8//! mapping a selection or decoration across an edit).
9//!
10//! Operational-transform style *rebasing* of concurrent edits is intentionally
11//! out of scope: it needs a bidirectional position map with insertion tie-breaks
12//! and stable node identity that the value/live-index [`Change`] model doesn't
13//! provide.
14
15use crate::diff::Change;
16use std::collections::HashMap;
17
18/// A change list apply-equivalent to running `a` then `b`.
19///
20/// Because [`apply`](crate::apply) folds changes in order against the live tree,
21/// `b`'s paths/indices already assume `a` has run — so plain concatenation is
22/// the semantic identity. `compose` returns that concatenation in [`compact`]ed
23/// form (redundant node-local ops coalesced).
24///
25/// ```
26/// use tiptap_rusty_parser::{apply, compose, Node};
27/// let base = Node::element("doc").with_child(Node::text("x"));
28/// let a = vec![tiptap_rusty_parser::Change::SetText { path: vec![0], text: Some("y".into()) }];
29/// let b = vec![tiptap_rusty_parser::Change::SetText { path: vec![0], text: Some("z".into()) }];
30/// let composed = compose(&a, &b);
31/// assert_eq!(composed.len(), 1); // the two SetTexts coalesced to the last
32/// let mut t = base.clone();
33/// apply(&mut t, &composed).unwrap();
34/// assert_eq!(t.text_content(), "z");
35/// ```
36pub fn compose(a: &[Change], b: &[Change]) -> Vec<Change> {
37 let mut all = Vec::with_capacity(a.len() + b.len());
38 all.extend_from_slice(a);
39 all.extend_from_slice(b);
40 compact(&all)
41}
42
43/// Identifies a node-local *field* write, so repeated writes to the same field
44/// can be coalesced (last-wins). Structural ops have no key.
45#[derive(PartialEq, Eq, Hash)]
46enum FieldKey {
47 Text(Vec<usize>),
48 Marks(Vec<usize>),
49 Attr(Vec<usize>, String),
50 Extra(Vec<usize>, String),
51}
52
53fn field_key(change: &Change) -> Option<FieldKey> {
54 match change {
55 Change::SetText { path, .. } => Some(FieldKey::Text(path.clone())),
56 Change::SetMarks { path, .. } => Some(FieldKey::Marks(path.clone())),
57 Change::SetAttr { path, key, .. } | Change::RemoveAttr { path, key } => {
58 Some(FieldKey::Attr(path.clone(), key.clone()))
59 }
60 Change::SetExtra { path, key, .. } | Change::RemoveExtra { path, key } => {
61 Some(FieldKey::Extra(path.clone(), key.clone()))
62 }
63 // Structural: Insert / Remove / Replace / Move.
64 _ => None,
65 }
66}
67
68/// Coalesce redundant changes while preserving the [`apply`](crate::apply)
69/// result. Only **safe** reductions are performed:
70///
71/// - repeated writes to the same node field (`SetText`/`SetMarks`, or
72/// `SetAttr`/`RemoveAttr` / `SetExtra`/`RemoveExtra` on the same key) collapse
73/// to the **last** one (each write fully determines that field's final value);
74/// - an `Insert` immediately followed by a `Remove` of that same just-inserted
75/// child cancels out.
76///
77/// Structural ops (`Insert`/`Remove`/`Move`/`Replace`) act as **barriers**:
78/// because [`apply`] resolves indices against the live tree, field ops are never
79/// coalesced across them. `compact(c)` is never longer than `c`.
80///
81/// Precondition: this preserves the `apply` result for change lists that apply
82/// **cleanly** to their intended base (as produced by [`diff`](crate::diff) /
83/// [`Transform`](crate::Transform)). For a deliberately invalid list it can
84/// differ — e.g. an out-of-bounds `Insert` immediately followed by its matching
85/// `Remove` cancels here, whereas applying the original would error; validity
86/// can't be checked from a change list alone.
87pub fn compact(changes: &[Change]) -> Vec<Change> {
88 let mut out: Vec<Change> = Vec::with_capacity(changes.len());
89 // (field key) -> index in `out` of the last kept write, within the current
90 // barrier segment. Cleared whenever a structural op is emitted.
91 let mut last: HashMap<FieldKey, usize> = HashMap::new();
92
93 for change in changes {
94 match field_key(change) {
95 Some(key) => {
96 if let Some(&idx) = last.get(&key) {
97 out[idx] = change.clone(); // last-wins, kept in place (segment-local)
98 } else {
99 last.insert(key, out.len());
100 out.push(change.clone());
101 }
102 }
103 None => {
104 // Adjacent Insert+Remove of the same child cancels out.
105 if let Change::Remove { path, index } = change {
106 if let Some(Change::Insert {
107 path: ip,
108 index: ii,
109 ..
110 }) = out.last()
111 {
112 if ip == path && ii == index {
113 out.pop();
114 last.clear();
115 continue;
116 }
117 }
118 }
119 out.push(change.clone());
120 last.clear(); // structural barrier
121 }
122 }
123 }
124 out
125}
126
127/// If `prefix` is a strict ancestor level of `q`, return that level's depth
128/// (so the structural op at parent `prefix` acts on `q[depth]`).
129fn affected_level(q: &[usize], prefix: &[usize]) -> Option<usize> {
130 if prefix.len() < q.len() && q[..prefix.len()] == *prefix {
131 Some(prefix.len())
132 } else {
133 None
134 }
135}
136
137/// Carry an index-path through a change list: where does the node originally at
138/// `path` end up after applying `changes`? Returns `None` if it was removed or
139/// replaced away.
140///
141/// Field changes never move nodes. Structural changes shift the index components
142/// of `path` at the level they act on (an `Insert` at or before the index shifts
143/// it right; a `Remove`/`Move` shifts accordingly; removing or replacing a node
144/// on the path drops it). This mirrors [`apply`](crate::apply)'s live-index
145/// semantics, so the mapped path addresses the same node in the applied tree.
146///
147/// ```
148/// use tiptap_rusty_parser::{map_path, Change};
149/// // A sibling inserted before index 1 shifts it to 2.
150/// let changes = vec![Change::Insert { path: vec![], index: 0, node: Default::default() }];
151/// assert_eq!(map_path(&[1, 0], &changes), Some(vec![2, 0]));
152/// // Removing the node on the path drops it.
153/// let removed = vec![Change::Remove { path: vec![], index: 1 }];
154/// assert_eq!(map_path(&[1, 0], &removed), None);
155/// ```
156pub fn map_path(path: &[usize], changes: &[Change]) -> Option<Vec<usize>> {
157 let mut q = path.to_vec();
158 for change in changes {
159 match change {
160 Change::Insert { path: p, index, .. } => {
161 if let Some(d) = affected_level(&q, p) {
162 if *index <= q[d] {
163 q[d] += 1;
164 }
165 }
166 }
167 Change::Remove { path: p, index } => {
168 if let Some(d) = affected_level(&q, p) {
169 if *index < q[d] {
170 q[d] -= 1;
171 } else if *index == q[d] {
172 return None; // the node on the path was removed
173 }
174 }
175 }
176 Change::Move { path: p, from, to } => {
177 if let Some(d) = affected_level(&q, p) {
178 let k = q[d];
179 if *from == k {
180 // The node on the path is the one being moved.
181 q[d] = *to;
182 } else {
183 // remove(from) then insert(to), in post-removal coords.
184 let after_remove = if *from < k { k - 1 } else { k };
185 q[d] = if *to <= after_remove {
186 after_remove + 1
187 } else {
188 after_remove
189 };
190 }
191 }
192 }
193 // Replacing a node at or above `q` discards `q`'s subtree.
194 Change::Replace { path: p, .. } if p.len() <= q.len() && q[..p.len()] == *p => {
195 return None;
196 }
197 // Field ops (and replaces elsewhere) never relocate a node.
198 _ => {}
199 }
200 }
201 Some(q)
202}