diff options
Diffstat (limited to 'vendor/pulldown-cmark/src/tree.rs')
| -rw-r--r-- | vendor/pulldown-cmark/src/tree.rs | 276 |
1 files changed, 276 insertions, 0 deletions
diff --git a/vendor/pulldown-cmark/src/tree.rs b/vendor/pulldown-cmark/src/tree.rs new file mode 100644 index 000000000..8e971bc20 --- /dev/null +++ b/vendor/pulldown-cmark/src/tree.rs @@ -0,0 +1,276 @@ +// Copyright 2018 Google LLC +// +// Use of this source code is governed by an MIT-style +// license that can be found in the LICENSE file or at +// https://opensource.org/licenses/MIT. + +//! A Vec-based container for a tree structure. + +use std::num::NonZeroUsize; +use std::ops::{Add, Sub}; + +use crate::parse::{Item, ItemBody}; + +#[derive(Debug, Eq, PartialEq, Copy, Clone, PartialOrd)] +pub(crate) struct TreeIndex(NonZeroUsize); + +impl TreeIndex { + fn new(i: usize) -> Self { + TreeIndex(NonZeroUsize::new(i).unwrap()) + } + + pub fn get(self) -> usize { + self.0.get() + } +} + +impl Add<usize> for TreeIndex { + type Output = TreeIndex; + + fn add(self, rhs: usize) -> Self { + let inner = self.0.get() + rhs; + TreeIndex::new(inner) + } +} + +impl Sub<usize> for TreeIndex { + type Output = TreeIndex; + + fn sub(self, rhs: usize) -> Self { + let inner = self.0.get().checked_sub(rhs).unwrap(); + TreeIndex::new(inner) + } +} + +#[derive(Debug, Clone, Copy)] +pub(crate) struct Node<T> { + pub child: Option<TreeIndex>, + pub next: Option<TreeIndex>, + pub item: T, +} + +/// A tree abstraction, intended for fast building as a preorder traversal. +#[derive(Clone)] +pub(crate) struct Tree<T> { + nodes: Vec<Node<T>>, + spine: Vec<TreeIndex>, // indices of nodes on path to current node + cur: Option<TreeIndex>, +} + +impl<T: Default> Tree<T> { + // Indices start at one, so we place a dummy value at index zero. + // The alternative would be subtracting one from every TreeIndex + // every time we convert it to usize to index our nodes. + pub(crate) fn with_capacity(cap: usize) -> Tree<T> { + let mut nodes = Vec::with_capacity(cap); + nodes.push(Node { + child: None, + next: None, + item: <T as Default>::default(), + }); + Tree { + nodes, + spine: Vec::new(), + cur: None, + } + } + + /// Returns the index of the element currently in focus. + pub(crate) fn cur(&self) -> Option<TreeIndex> { + self.cur + } + + /// Append one item to the current position in the tree. + pub(crate) fn append(&mut self, item: T) -> TreeIndex { + let ix = self.create_node(item); + let this = Some(ix); + + if let Some(ix) = self.cur { + self[ix].next = this; + } else if let Some(&parent) = self.spine.last() { + self[parent].child = this; + } + self.cur = this; + ix + } + + /// Create an isolated node. + pub(crate) fn create_node(&mut self, item: T) -> TreeIndex { + let this = self.nodes.len(); + self.nodes.push(Node { + child: None, + next: None, + item, + }); + TreeIndex::new(this) + } + + /// Push down one level, so that new items become children of the current node. + /// The new focus index is returned. + pub(crate) fn push(&mut self) -> TreeIndex { + let cur_ix = self.cur.unwrap(); + self.spine.push(cur_ix); + self.cur = self[cur_ix].child; + cur_ix + } + + /// Pop back up a level. + pub(crate) fn pop(&mut self) -> Option<TreeIndex> { + let ix = Some(self.spine.pop()?); + self.cur = ix; + ix + } + + /// Look at the parent node. + pub(crate) fn peek_up(&self) -> Option<TreeIndex> { + self.spine.last().copied() + } + + /// Look at grandparent node. + pub(crate) fn peek_grandparent(&self) -> Option<TreeIndex> { + if self.spine.len() >= 2 { + Some(self.spine[self.spine.len() - 2]) + } else { + None + } + } + + /// Returns true when there are no nodes other than the root node + /// in the tree, false otherwise. + pub(crate) fn is_empty(&self) -> bool { + self.nodes.len() <= 1 + } + + /// Returns the length of the spine. + pub(crate) fn spine_len(&self) -> usize { + self.spine.len() + } + + /// Resets the focus to the first node added to the tree, if it exists. + pub(crate) fn reset(&mut self) { + self.cur = if self.is_empty() { + None + } else { + Some(TreeIndex::new(1)) + }; + self.spine.clear(); + } + + /// Walks the spine from a root node up to, but not including, the current node. + pub(crate) fn walk_spine(&self) -> impl std::iter::DoubleEndedIterator<Item = &TreeIndex> { + self.spine.iter() + } + + /// Moves focus to the next sibling of the given node. + pub(crate) fn next_sibling(&mut self, cur_ix: TreeIndex) -> Option<TreeIndex> { + self.cur = self[cur_ix].next; + self.cur + } +} + +impl Tree<Item> { + /// Truncates the preceding siblings to the given end position, + /// and returns the new current node. + pub(crate) fn truncate_siblings(&mut self, bytes: &[u8], end_byte_ix: usize) { + let parent_ix = self.peek_up().unwrap(); + let mut next_child_ix = self[parent_ix].child; + let mut prev_child_ix = None; + + // drop or truncate children based on its range + while let Some(child_ix) = next_child_ix { + let child_end = self[child_ix].item.end; + if child_end < end_byte_ix { + // preserve this node, and go to the next + prev_child_ix = Some(child_ix); + next_child_ix = self[child_ix].next; + continue; + } else if child_end == end_byte_ix { + // this will be the last node + self[child_ix].next = None; + // focus to the new last child (this node) + self.cur = Some(child_ix); + } else if self[child_ix].item.start == end_byte_ix { + // check whether the previous character is a backslash + let is_previous_char_backslash_escape = + end_byte_ix.checked_sub(1).map_or(false, |prev| { + (bytes[prev] == b'\\') && (self[child_ix].item.body == ItemBody::Text) + }); + if is_previous_char_backslash_escape { + // rescue the backslash as a plain text content + let last_byte_ix = end_byte_ix - 1; + self[child_ix].item.start = last_byte_ix; + self[child_ix].item.end = end_byte_ix; + self.cur = Some(child_ix); + } else if let Some(prev_child_ix) = prev_child_ix { + // the node will become empty. drop the node + // a preceding sibling exists + self[prev_child_ix].next = None; + self.cur = Some(prev_child_ix); + } else { + // no preceding siblings. remove the node from the parent + self[parent_ix].child = None; + self.cur = None; + } + } else { + debug_assert!(self[child_ix].item.start < end_byte_ix); + debug_assert!(end_byte_ix < child_end); + // truncate the node + self[child_ix].item.end = end_byte_ix; + self[child_ix].next = None; + // focus to the new last child + self.cur = Some(child_ix); + } + break; + } + } +} + +impl<T> std::fmt::Debug for Tree<T> +where + T: std::fmt::Debug, +{ + fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { + fn debug_tree<T>( + tree: &Tree<T>, + cur: TreeIndex, + indent: usize, + f: &mut std::fmt::Formatter, + ) -> std::fmt::Result + where + T: std::fmt::Debug, + { + for _ in 0..indent { + write!(f, " ")?; + } + writeln!(f, "{:?}", &tree[cur].item)?; + if let Some(child_ix) = tree[cur].child { + debug_tree(tree, child_ix, indent + 1, f)?; + } + if let Some(next_ix) = tree[cur].next { + debug_tree(tree, next_ix, indent, f)?; + } + Ok(()) + } + + if self.nodes.len() > 1 { + let cur = TreeIndex(NonZeroUsize::new(1).unwrap()); + debug_tree(self, cur, 0, f) + } else { + write!(f, "Empty tree") + } + } +} + +impl<T> std::ops::Index<TreeIndex> for Tree<T> { + type Output = Node<T>; + + fn index(&self, ix: TreeIndex) -> &Self::Output { + self.nodes.index(ix.get()) + } +} + +impl<T> std::ops::IndexMut<TreeIndex> for Tree<T> { + fn index_mut(&mut self, ix: TreeIndex) -> &mut Node<T> { + self.nodes.index_mut(ix.get()) + } +} |