pulldown_cmark/
tree.rs

Help
1// Copyright 2018 Google LLC
2//
3// Use of this source code is governed by an MIT-style
4// license that can be found in the LICENSE file or at
5// https://opensource.org/licenses/MIT.
6
7//! A Vec-based container for a tree structure.
8
9use std::num::NonZeroUsize;
10use std::ops::{Add, Sub};
11
12use crate::parse::{Item, ItemBody};
13
14#[derive(Debug, Eq, PartialEq, Copy, Clone, PartialOrd)]
15pub(crate) struct TreeIndex(NonZeroUsize);
16
17impl TreeIndex {
18    fn new(i: usize) -> Self {
19        TreeIndex(NonZeroUsize::new(i).unwrap())
20    }
21
22    pub fn get(self) -> usize {
23        self.0.get()
24    }
25}
26
27impl Add<usize> for TreeIndex {
28    type Output = TreeIndex;
29
30    fn add(self, rhs: usize) -> Self {
31        let inner = self.0.get() + rhs;
32        TreeIndex::new(inner)
33    }
34}
35
36impl Sub<usize> for TreeIndex {
37    type Output = TreeIndex;
38
39    fn sub(self, rhs: usize) -> Self {
40        let inner = self.0.get().checked_sub(rhs).unwrap();
41        TreeIndex::new(inner)
42    }
43}
44
45#[derive(Debug, Clone, Copy)]
46pub(crate) struct Node<T> {
47    pub child: Option<TreeIndex>,
48    pub next: Option<TreeIndex>,
49    pub item: T,
50}
51
52/// A tree abstraction, intended for fast building as a preorder traversal.
53#[derive(Clone)]
54pub(crate) struct Tree<T> {
55    nodes: Vec<Node<T>>,
56    spine: Vec<TreeIndex>, // indices of nodes on path to current node
57    cur: Option<TreeIndex>,
58}
59
60impl<T: Default> Tree<T> {
61    // Indices start at one, so we place a dummy value at index zero.
62    // The alternative would be subtracting one from every TreeIndex
63    // every time we convert it to usize to index our nodes.
64    pub(crate) fn with_capacity(cap: usize) -> Tree<T> {
65        let mut nodes = Vec::with_capacity(cap);
66        nodes.push(Node {
67            child: None,
68            next: None,
69            item: <T as Default>::default(),
70        });
71        Tree {
72            nodes,
73            spine: Vec::new(),
74            cur: None,
75        }
76    }
77
78    /// Returns the index of the element currently in focus.
79    pub(crate) fn cur(&self) -> Option<TreeIndex> {
80        self.cur
81    }
82
83    /// Append one item to the current position in the tree.
84    pub(crate) fn append(&mut self, item: T) -> TreeIndex {
85        let ix = self.create_node(item);
86        let this = Some(ix);
87
88        if let Some(ix) = self.cur {
89            self[ix].next = this;
90        } else if let Some(&parent) = self.spine.last() {
91            self[parent].child = this;
92        }
93        self.cur = this;
94        ix
95    }
96
97    /// Create an isolated node.
98    pub(crate) fn create_node(&mut self, item: T) -> TreeIndex {
99        let this = self.nodes.len();
100        self.nodes.push(Node {
101            child: None,
102            next: None,
103            item,
104        });
105        TreeIndex::new(this)
106    }
107
108    /// Push down one level, so that new items become children of the current node.
109    /// The new focus index is returned.
110    pub(crate) fn push(&mut self) -> TreeIndex {
111        let cur_ix = self.cur.unwrap();
112        self.spine.push(cur_ix);
113        self.cur = self[cur_ix].child;
114        cur_ix
115    }
116
117    /// Pop back up a level.
118    pub(crate) fn pop(&mut self) -> Option<TreeIndex> {
119        let ix = Some(self.spine.pop()?);
120        self.cur = ix;
121        ix
122    }
123
124    /// Remove the last node, as `pop` but removing it.
125    pub(crate) fn remove_node(&mut self) -> Option<TreeIndex> {
126        let ix = self.spine.pop()?;
127        self.cur = Some(ix);
128        self.nodes.pop()?;
129        self[ix].child = None;
130        Some(ix)
131    }
132
133    /// Look at the parent node.
134    pub(crate) fn peek_up(&self) -> Option<TreeIndex> {
135        self.spine.last().copied()
136    }
137
138    /// Look at grandparent node.
139    pub(crate) fn peek_grandparent(&self) -> Option<TreeIndex> {
140        if self.spine.len() >= 2 {
141            Some(self.spine[self.spine.len() - 2])
142        } else {
143            None
144        }
145    }
146
147    /// Returns true when there are no nodes other than the root node
148    /// in the tree, false otherwise.
149    pub(crate) fn is_empty(&self) -> bool {
150        self.nodes.len() <= 1
151    }
152
153    /// Returns the length of the spine.
154    pub(crate) fn spine_len(&self) -> usize {
155        self.spine.len()
156    }
157
158    /// Resets the focus to the first node added to the tree, if it exists.
159    pub(crate) fn reset(&mut self) {
160        self.cur = if self.is_empty() {
161            None
162        } else {
163            Some(TreeIndex::new(1))
164        };
165        self.spine.clear();
166    }
167
168    /// Walks the spine from a root node up to, but not including, the current node.
169    pub(crate) fn walk_spine(&self) -> impl std::iter::DoubleEndedIterator<Item = &TreeIndex> {
170        self.spine.iter()
171    }
172
173    /// Moves focus to the next sibling of the given node.
174    pub(crate) fn next_sibling(&mut self, cur_ix: TreeIndex) -> Option<TreeIndex> {
175        self.cur = self[cur_ix].next;
176        self.cur
177    }
178
179    pub(crate) fn truncate_to_parent(&mut self, child_ix: TreeIndex) {
180        let next = self[child_ix].next;
181        self[child_ix].next = None;
182        if let Some(cur) = self.cur {
183            self[cur].next = next;
184        } else if let Some(&parent) = self.spine.last() {
185            self[parent].child = next;
186        }
187        if next.is_some() {
188            self.cur = next;
189        } else {
190            self.pop();
191        }
192    }
193}
194
195impl Tree<Item> {
196    /// Truncates the preceding siblings to the given end position,
197    /// and returns the new current node.
198    pub(crate) fn truncate_siblings(&mut self, end_byte_ix: usize) {
199        let parent_ix = self.peek_up().unwrap();
200        let mut next_child_ix = self[parent_ix].child;
201        let mut prev_child_ix = None;
202
203        // drop or truncate children based on its range
204        while let Some(child_ix) = next_child_ix {
205            let child_end = self[child_ix].item.end;
206            if child_end < end_byte_ix {
207                // preserve this node, and go to the next
208                prev_child_ix = Some(child_ix);
209                next_child_ix = self[child_ix].next;
210                continue;
211            } else if child_end == end_byte_ix {
212                // this will be the last node
213                self[child_ix].next = None;
214                // focus to the new last child (this node)
215                self.cur = Some(child_ix);
216            } else if self[child_ix].item.start == end_byte_ix {
217                // check whether the previous character is a backslash
218                let is_previous_char_backslash_escape = match self[child_ix].item.body {
219                    ItemBody::Text { backslash_escaped } => backslash_escaped,
220                    _ => false,
221                };
222                if is_previous_char_backslash_escape {
223                    // rescue the backslash as a plain text content
224                    let last_byte_ix = end_byte_ix - 1;
225                    self[child_ix].item.start = last_byte_ix;
226                    self[child_ix].item.end = end_byte_ix;
227                    self.cur = Some(child_ix);
228                } else if let Some(prev_child_ix) = prev_child_ix {
229                    // the node will become empty. drop the node
230                    // a preceding sibling exists
231                    self[prev_child_ix].next = None;
232                    self.cur = Some(prev_child_ix);
233                } else {
234                    // no preceding siblings. remove the node from the parent
235                    self[parent_ix].child = None;
236                    self.cur = None;
237                }
238            } else {
239                debug_assert!(self[child_ix].item.start < end_byte_ix);
240                debug_assert!(end_byte_ix < child_end);
241                // truncate the node
242                self[child_ix].item.end = end_byte_ix;
243                self[child_ix].next = None;
244                // focus to the new last child
245                self.cur = Some(child_ix);
246            }
247            break;
248        }
249    }
250}
251
252impl<T> std::fmt::Debug for Tree<T>
253where
254    T: std::fmt::Debug,
255{
256    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
257        fn debug_tree<T>(
258            tree: &Tree<T>,
259            cur: TreeIndex,
260            indent: usize,
261            f: &mut std::fmt::Formatter<'_>,
262        ) -> std::fmt::Result
263        where
264            T: std::fmt::Debug,
265        {
266            for _ in 0..indent {
267                write!(f, "  ")?;
268            }
269            writeln!(f, "{:?}", &tree[cur].item)?;
270            if let Some(child_ix) = tree[cur].child {
271                debug_tree(tree, child_ix, indent + 1, f)?;
272            }
273            if let Some(next_ix) = tree[cur].next {
274                debug_tree(tree, next_ix, indent, f)?;
275            }
276            Ok(())
277        }
278
279        if self.nodes.len() > 1 {
280            let cur = TreeIndex(NonZeroUsize::new(1).unwrap());
281            debug_tree(self, cur, 0, f)
282        } else {
283            write!(f, "Empty tree")
284        }
285    }
286}
287
288impl<T> std::ops::Index<TreeIndex> for Tree<T> {
289    type Output = Node<T>;
290
291    fn index(&self, ix: TreeIndex) -> &Self::Output {
292        self.nodes.index(ix.get())
293    }
294}
295
296impl<T> std::ops::IndexMut<TreeIndex> for Tree<T> {
297    fn index_mut(&mut self, ix: TreeIndex) -> &mut Node<T> {
298        self.nodes.index_mut(ix.get())
299    }
300}
pulldown_cmark/tree.rs

pulldown_cmark/
tree.rs
