扁平数组上的树

#[derive(Debug, Eq, PartialEq, Copy, Clone, PartialOrd)]
pub(crate) struct TreeIndex(NonZeroUsize);

#[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>,
}

TreeIndex           8 bytes
Option<TreeIndex>   8 bytes
Item               32 bytes
ItemBody           16 bytes
Node<Item>         48 bytes
Option<usize>      16 bytes
enum Nil|Valid(NZ)  8 bytes

    // 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(),
        });
        // ...
    }

    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
    }

    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
    }

    pub(crate) fn pop(&mut self) -> Option<TreeIndex> {
        let ix = Some(self.spine.pop()?);
        self.cur = ix;
        ix
    }

  0 child=-   next=-     0..0   Root
  1 child=2   next=7     0..34  Heading(H1, None) "# 拉取式解析：*pu...
  2 child=-   next=3     2..20  Text { backslash_escaped: false } "拉取式解析："
  3 child=-   next=4    20..21  MaybeEmphasis(1, true, false) "*"
  4 child=-   next=5    21..25  Text { backslash_escaped: false } "pull"
  5 child=-   next=6    25..26  MaybeEmphasis(1, false, true) "*"
  6 child=-   next=-    26..33  Text { backslash_escaped: false } " parser"
  7 child=8   next=24   35..125 Paragraph "pulldown-cmark 把 Mark...
...
 24 child=25  next=35  126..208 List(Cell { value: ListFlags(IS_TIGHT) }, 45, 0) "- 第一遍：扫行，...
 25 child=26  next=28  126..159 ListItem(2) "- 第一遍：扫行，...
 26 child=27  next=-   128..159 TightParagraph "第一遍：扫行，建...
 27 child=-   next=-   128..158 Text { backslash_escaped: false } "第一遍：扫行，建...
 28 child=29  next=-   159..208 ListItem(2) "- 第二遍：`Parser::...
...

    fn next(&mut self) -> Option<Event<'a>> {
        match self.tree.cur() {
            None => {
                let ix = self.tree.pop()?;
                // ...
                let tag_end = body_to_tag_end(&self.tree[ix].item.body);
                self.tree.next_sibling(ix);
                Some(Event::End(tag_end))
            }
            Some(cur_ix) => {
                // ...
                    if self.tree[cur_ix].item.body.is_maybe_inline() {
                        self.handle_inline();
                    }

                    let item = self.tree[cur_ix].item.clone();
                    let event = item_to_event(&item, self.text, &mut self.allocs);
                    if let Event::Start(ref _tag) = event {
                        self.tree.push();
                    } else {
                        self.tree.next_sibling(cur_ix);
                    }
                    Some(event)
                // ...
            }
        }
    }

== nodes ==
  0 child=-   next=-     0..0   Root
  1 child=2   next=-     0..21  Heading(H2, Some(HeadingIndex(1))) "Foo *bar* {#top}\n---\n"
  2 child=-   next=3     0..4   Text { backslash_escaped: false } "Foo "
  3 child=-   next=4     4..5   MaybeEmphasis(1, true, false) "*"
  4 child=-   next=5     5..8   Text { backslash_escaped: false } "bar"
  5 child=-   next=-     8..9   MaybeEmphasis(1, false, true) "*"
  6 child=-   next=-     9..16  Text { backslash_escaped: false } " {#top}"
== tree ==
Item { start: 0, end: 21, body: Heading(H2, Some(HeadingIndex(1))) }
  Item { start: 0, end: 4, body: Text { backslash_escaped: false } }
  Item { start: 4, end: 5, body: MaybeEmphasis(1, true, false) }
  Item { start: 5, end: 8, body: Text { backslash_escaped: false } }
  Item { start: 8, end: 9, body: MaybeEmphasis(1, false, true) }