ktrs_syntax/tree/
mod.rs

1//! [`Tree`]: a parsed file as flat preorder arrays. An element (node or token) is its preorder
2//! index; navigation is index arithmetic, and token text is a slice of the source. Replaces rowan's
3//! green/red trees, which allocate per node when built and per step when walked (see
4//! research/06-tree-library.md for the measurements).
5
6mod builder;
7mod kind_scan;
8
9pub use builder::TreeBuilder;
10pub use kind_scan::KindScan;
11
12use crate::{SyntaxKind, TextRange, TextSize};
13
14/// Preorder index of an element in its [`Tree`].
15pub type ElementId = u32;
16
17const NONE: u32 = u32::MAX;
18/// Tokens and childless nodes both span one preorder slot; the kind's top bit tells them apart.
19const TOKEN_BIT: u16 = 0x8000;
20
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct Tree {
23    text: Box<str>,
24    kinds: Vec<u16>,
25    starts: Vec<u32>,
26    /// Preorder index one past the element's subtree.
27    ends: Vec<u32>,
28    parents: Vec<u32>,
29    prev_sibs: Vec<u32>,
30}
31
32impl Tree {
33    pub const ROOT: ElementId = 0;
34
35    /// The whole source text.
36    pub fn text(&self) -> &str {
37        &self.text
38    }
39
40    /// Number of elements (nodes and tokens).
41    pub fn len(&self) -> usize {
42        self.kinds.len()
43    }
44
45    pub fn is_empty(&self) -> bool {
46        self.kinds.is_empty()
47    }
48
49    pub fn kind(&self, e: ElementId) -> SyntaxKind {
50        SyntaxKind::from_raw(self.kinds[e as usize] & !TOKEN_BIT)
51    }
52
53    pub fn is_token(&self, e: ElementId) -> bool {
54        self.kinds[e as usize] & TOKEN_BIT != 0
55    }
56
57    /// One past the last element of `e`'s subtree, in preorder.
58    pub fn subtree_end(&self, e: ElementId) -> ElementId {
59        self.ends[e as usize]
60    }
61
62    pub fn parent(&self, e: ElementId) -> Option<ElementId> {
63        some(self.parents[e as usize])
64    }
65
66    pub fn first_child(&self, e: ElementId) -> Option<ElementId> {
67        (self.ends[e as usize] > e + 1).then_some(e + 1)
68    }
69
70    pub fn last_child(&self, e: ElementId) -> Option<ElementId> {
71        let mut last = self.first_child(e)?;
72        // The subtree's last element is a descendant of the last child; climb to it.
73        let mut cur = self.ends[e as usize] - 1;
74        while let Some(p) = self.parent(cur) {
75            if p == e {
76                last = cur;
77                break;
78            }
79            cur = p;
80        }
81        Some(last)
82    }
83
84    pub fn next_sibling(&self, e: ElementId) -> Option<ElementId> {
85        let parent = self.parent(e)?;
86        let next = self.ends[e as usize];
87        (next < self.ends[parent as usize]).then_some(next)
88    }
89
90    pub fn prev_sibling(&self, e: ElementId) -> Option<ElementId> {
91        some(self.prev_sibs[e as usize])
92    }
93
94    pub fn children(&self, e: ElementId) -> Children<'_> {
95        Children { tree: self, next: self.first_child(e) }
96    }
97
98    pub fn text_range(&self, e: ElementId) -> TextRange {
99        let start = self.starts[e as usize];
100        let end = self.starts.get(self.ends[e as usize] as usize).copied().unwrap_or(self.text.len() as u32);
101        TextRange::new(TextSize::from(start), TextSize::from(end))
102    }
103
104    pub fn text_of(&self, e: ElementId) -> &str {
105        &self.text[self.text_range(e)]
106    }
107
108    /// Whether any element strictly inside `e`'s subtree has `kind`.
109    pub fn has_descendant_of_kind(&self, e: ElementId, kind: SyntaxKind) -> bool {
110        let raw = kind as u16;
111        self.kinds[e as usize + 1..self.ends[e as usize] as usize].iter().any(|&k| k & !TOKEN_BIT == raw)
112    }
113
114    /// The elements of `e`'s subtree (`e` included), in preorder, that are nodes of one of `nodes` or
115    /// tokens of one of `tokens`: a scan of the raw kind words, cheaper than a `kind`/`is_token` walk.
116    pub fn find_kinds<const N: usize, const M: usize>(
117        &self,
118        e: ElementId,
119        nodes: [SyntaxKind; N],
120        tokens: [SyntaxKind; M],
121    ) -> KindScan<'_> {
122        const { assert!(N + M <= kind_scan::MAX_WANTED) };
123        let mut wanted = [kind_scan::NEVER; kind_scan::MAX_WANTED];
124        for (slot, k) in wanted.iter_mut().zip(nodes.map(|k| k as u16).into_iter().chain(tokens.map(|k| k as u16 | TOKEN_BIT))) {
125            *slot = k;
126        }
127        let start = e as usize;
128        KindScan::new(&self.kinds[start..self.ends[start] as usize], start, wanted)
129    }
130}
131
132pub struct Children<'t> {
133    tree: &'t Tree,
134    next: Option<ElementId>,
135}
136
137impl Iterator for Children<'_> {
138    type Item = ElementId;
139
140    fn next(&mut self) -> Option<ElementId> {
141        let cur = self.next?;
142        self.next = self.tree.next_sibling(cur);
143        Some(cur)
144    }
145}
146
147fn some(index: u32) -> Option<ElementId> {
148    (index != NONE).then_some(index)
149}
150
151#[cfg(test)]
152mod tests;
ktrs_syntax/tree/mod.rs

ktrs_syntax/tree/
mod.rs
