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: usize = 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: usize = 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
180impl Tree<Item> {
181 /// Truncates the preceding siblings to the given end position,
182 /// and returns the new current node.
183 pub(crate) fn truncate_siblings(&mut self, end_byte_ix: usize) {
184 let parent_ix = self.peek_up().unwrap();
185 let mut next_child_ix = self[parent_ix].child;
186 let mut prev_child_ix = None;
187
188 // drop or truncate children based on its range
189 while let Some(child_ix) = next_child_ix {
190 let child_end = self[child_ix].item.end;
191 if child_end < end_byte_ix {
192 // preserve this node, and go to the next
193 prev_child_ix = Some(child_ix);
194 next_child_ix = self[child_ix].next;
195 continue;
196 } else if child_end == end_byte_ix {
197 // this will be the last node
198 self[child_ix].next = None;
199 // focus to the new last child (this node)
200 self.cur = Some(child_ix);
201 } else if self[child_ix].item.start == end_byte_ix {
202 // check whether the previous character is a backslash
203 let is_previous_char_backslash_escape = match self[child_ix].item.body {
204 ItemBody::Text { backslash_escaped } => backslash_escaped,
205 _ => false,
206 };
207 if is_previous_char_backslash_escape {
208 // rescue the backslash as a plain text content
209 let last_byte_ix = end_byte_ix - 1;
210 self[child_ix].item.start = last_byte_ix;
211 self[child_ix].item.end = end_byte_ix;
212 self.cur = Some(child_ix);
213 } else if let Some(prev_child_ix) = prev_child_ix {
214 // the node will become empty. drop the node
215 // a preceding sibling exists
216 self[prev_child_ix].next = None;
217 self.cur = Some(prev_child_ix);
218 } else {
219 // no preceding siblings. remove the node from the parent
220 self[parent_ix].child = None;
221 self.cur = None;
222 }
223 } else {
224 debug_assert!(self[child_ix].item.start < end_byte_ix);
225 debug_assert!(end_byte_ix < child_end);
226 // truncate the node
227 self[child_ix].item.end = end_byte_ix;
228 self[child_ix].next = None;
229 // focus to the new last child
230 self.cur = Some(child_ix);
231 }
232 break;
233 }
234 }
235}
236
237impl<T> std::fmt::Debug for Tree<T>
238where
239 T: std::fmt::Debug,
240{
241 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
242 fn debug_tree<T>(
243 tree: &Tree<T>,
244 cur: TreeIndex,
245 indent: usize,
246 f: &mut std::fmt::Formatter<'_>,
247 ) -> std::fmt::Result
248 where
249 T: std::fmt::Debug,
250 {
251 for _ in 0..indent {
252 write!(f, " ")?;
253 }
254 writeln!(f, "{:?}", &tree[cur].item)?;
255 if let Some(child_ix) = tree[cur].child {
256 debug_tree(tree, child_ix, indent + 1, f)?;
257 }
258 if let Some(next_ix) = tree[cur].next {
259 debug_tree(tree, next_ix, indent, f)?;
260 }
261 Ok(())
262 }
263
264 if self.nodes.len() > 1 {
265 let cur = TreeIndex(NonZeroUsize::new(1).unwrap());
266 debug_tree(self, cur, 0, f)
267 } else {
268 write!(f, "Empty tree")
269 }
270 }
271}
272
273impl<T> std::ops::Index<TreeIndex> for Tree<T> {
274 type Output = Node<T>;
275
276 fn index(&self, ix: TreeIndex) -> &Self::Output {
277 self.nodes.index(ix.get())
278 }
279}
280
281impl<T> std::ops::IndexMut<TreeIndex> for Tree<T> {
282 fn index_mut(&mut self, ix: TreeIndex) -> &mut Node<T> {
283 self.nodes.index_mut(index:ix.get())
284 }
285}
286