syntree/
edit.rs

1//! Types associated with performing immutable editing of a tree.
2
3use core::marker::PhantomData;
4
5use alloc::vec::Vec;
6
7use std::collections::HashMap;
8
9use crate::builder::Builder;
10use crate::error::Error;
11use crate::flavor::Flavor;
12use crate::node::Node;
13use crate::tree::Tree;
14
15#[derive(Debug)]
16pub(crate) enum Change {
17    /// Delete the given node.
18    Delete,
19}
20
21/// A recorded set of tree modifications.
22///
23/// You can use [`ChangeSet::modify`] to construct a new modified tree from an
24/// existing one.
25///
26/// # Examples
27///
28/// ```
29/// use syntree::edit::ChangeSet;
30///
31/// let tree = syntree::tree! {
32///     "root" => {
33///         "child" => {
34///             ("lit", 1),
35///             ("lit", 2),
36///         },
37///         ("whitespace", 3),
38///     }
39/// };
40///
41/// let child = tree.first().and_then(|n| n.first()).ok_or("missing child")?;
42///
43/// let mut change_set = ChangeSet::new();
44/// change_set.remove(child.id());
45///
46/// assert_eq!(
47///     change_set.modify(&tree)?,
48///     syntree::tree! {
49///         "root" => {
50///             ("whitespace", 3)
51///         }
52///     }
53/// );
54///
55/// let lit = child.first().ok_or("missing lit")?;
56///
57/// let mut change_set = ChangeSet::new();
58/// change_set.remove(lit.id());
59///
60/// assert_eq!(
61///     change_set.modify(&tree)?,
62///     syntree::tree! {
63///         "root" => {
64///             "child" => {
65///                 ("lit", 2),
66///             },
67///             ("whitespace", 3)
68///         }
69///     }
70/// );
71/// # Ok::<_, Box<dyn core::error::Error>>(())
72/// ```
73pub struct ChangeSet<T, F>
74where
75    T: Copy,
76    F: Flavor,
77{
78    changes: HashMap<F::Pointer, Change>,
79    _marker: PhantomData<T>,
80}
81
82impl<T, F> ChangeSet<T, F>
83where
84    T: Copy,
85    F: Flavor,
86{
87    /// Construct a new empty [`ChangeSet`].
88    #[must_use]
89    pub fn new() -> Self {
90        Self::default()
91    }
92}
93
94impl<T, F> ChangeSet<T, F>
95where
96    T: Copy,
97    F: Flavor,
98{
99    /// Register a node removal in the changeset. Only one kind of modification
100    /// for a given node will be preserved.
101    ///
102    /// # Examples
103    ///
104    /// ```
105    /// use syntree::edit::ChangeSet;
106    ///
107    /// let tree = syntree::tree! {
108    ///     "root" => {
109    ///         "child" => {
110    ///             ("lit", 1),
111    ///             ("lit", 2),
112    ///         },
113    ///         ("whitespace", 3),
114    ///     }
115    /// };
116    ///
117    /// let child = tree.first().and_then(|n| n.first()).ok_or("missing child")?;
118    ///
119    /// let mut change_set = ChangeSet::new();
120    /// change_set.remove(child.id());
121    ///
122    /// assert_eq!(
123    ///     change_set.modify(&tree)?,
124    ///     syntree::tree! {
125    ///         "root" => {
126    ///             ("whitespace", 3)
127    ///         }
128    ///     }
129    /// );
130    /// # Ok::<_, Box<dyn core::error::Error>>(())
131    /// ```
132    pub fn remove(&mut self, id: F::Pointer) {
133        self.changes.insert(id, Change::Delete);
134    }
135
136    /// Construct a modified tree where the recorded modifications have been
137    /// applied.
138    ///
139    /// # Errors
140    ///
141    /// Errors with [`Error::Overflow`] in case we run out of node
142    /// identifiers.
143    ///
144    /// # Examples
145    ///
146    /// ```
147    /// use syntree::edit::ChangeSet;
148    ///
149    /// let tree = syntree::tree! {
150    ///     "root" => {
151    ///         "child" => {
152    ///             ("lit", 1),
153    ///             ("lit", 2),
154    ///         },
155    ///         ("whitespace", 3),
156    ///     }
157    /// };
158    ///
159    /// let child = tree.first().and_then(|n| n.first()).ok_or("missing child")?;
160    /// let mut change_set = ChangeSet::new();
161    /// change_set.remove(child.id());
162    ///
163    /// assert_eq!(
164    ///     change_set.modify(&tree)?,
165    ///     syntree::tree! {
166    ///         "root" => {
167    ///             ("whitespace", 3)
168    ///         }
169    ///     }
170    /// );
171    /// # Ok::<_, Box<dyn core::error::Error>>(())
172    /// ```
173    pub fn modify(&mut self, tree: &Tree<T, F>) -> Result<Tree<T, F>, Error<F::Error>> {
174        let mut output = Builder::<T, F>::with_capacity(tree.capacity())?;
175        let mut parents = Vec::<Node<'_, T, F>>::new();
176        let mut current = tree.first();
177
178        loop {
179            let Some(node) = current else {
180                let Some(parent) = parents.pop() else {
181                    break;
182                };
183
184                output.close()?;
185                current = parent.next();
186                continue;
187            };
188
189            if let Some(Change::Delete) = self.changes.get(&node.id()) {
190                current = node.next();
191                continue;
192            }
193
194            if let Some(first) = node.first() {
195                output.open(node.value())?;
196                parents.push(node);
197                current = Some(first);
198            } else {
199                // Leaves are laid out back-to-back, so removed spans are
200                // compacted away.
201                output.token(node.value(), node.span().len())?;
202                current = node.next();
203            }
204        }
205
206        output.build()
207    }
208}
209
210impl<T, F> Default for ChangeSet<T, F>
211where
212    T: Copy,
213    F: Flavor,
214{
215    #[inline]
216    fn default() -> Self {
217        Self {
218            changes: HashMap::new(),
219            _marker: PhantomData,
220        }
221    }
222}
syntree/edit.rs

syntree/
edit.rs
