tree_house/
lib.rs

1use locals::Locals;
2use ropey::RopeSlice;
3
4use slab::Slab;
5
6use std::fmt;
7use std::hash::{Hash, Hasher};
8use std::time::Duration;
9use tree_sitter::{IncompatibleGrammarError, Node, Tree};
10
11pub use crate::config::{read_query, LanguageConfig, LanguageLoader};
12pub use crate::injections_query::{InjectionLanguageMarker, InjectionsQuery};
13use crate::parse::LayerUpdateFlags;
14pub use crate::query_iter::{CapturedMatch, QueryMatchIter, QueryMatchIterEvent};
15pub use crate::tree_cursor::TreeCursor;
16pub use tree_sitter;
17// pub use pretty_print::pretty_print_tree;
18// pub use tree_cursor::TreeCursor;
19
20mod config;
21pub mod highlighter;
22mod injections_query;
23mod parse;
24#[cfg(all(test, feature = "fixtures"))]
25mod tests;
26// mod pretty_print;
27#[cfg(feature = "fixtures")]
28pub mod fixtures;
29pub mod locals;
30pub mod query_iter;
31pub mod text_object;
32mod tree_cursor;
33
34/// A layer represents a single a single syntax tree that represents (part of)
35/// a file parsed with a tree-sitter grammar. See [`Syntax`].
36#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
37pub struct Layer(u32);
38
39impl Layer {
40    fn idx(self) -> usize {
41        self.0 as usize
42    }
43}
44
45#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
46pub struct Language(pub u32);
47
48impl Language {
49    pub fn new(idx: u32) -> Language {
50        Language(idx)
51    }
52
53    pub fn idx(self) -> usize {
54        self.0 as usize
55    }
56}
57
58/// The Tree sitter syntax tree for a single language.
59///
60/// This is really multiple (nested) different syntax trees due to tree sitter
61/// injections. A single syntax tree/parser is called layer. Each layer
62/// is parsed as a single "file" by tree sitter. There can be multiple layers
63/// for the same language. A layer corresponds to one of three things:
64/// * the root layer
65/// * a singular injection limited to a single node in its parent layer
66/// * Multiple injections (multiple disjoint nodes in parent layer) that are
67///   parsed as though they are a single uninterrupted file.
68///
69/// An injection always refer to a single node into which another layer is
70/// injected. As injections only correspond to syntax tree nodes injections in
71/// the same layer do not intersect. However, the syntax tree in a an injected
72/// layer can have nodes that intersect with nodes from the parent layer. For
73/// example:
74///
75/// ``` no-compile
76/// layer2: | Sibling A |      Sibling B (layer3)     | Sibling C |
77/// layer1: | Sibling A (layer2) | Sibling B | Sibling C (layer2) |
78/// ````
79///
80/// In this case Sibling B really spans across a "GAP" in layer2. While the syntax
81/// node can not be split up by tree sitter directly, we can treat Sibling B as two
82/// separate injections. That is done while parsing/running the query capture. As
83/// a result the injections form a tree. Note that such other queries must account for
84/// such multi injection nodes.
85#[derive(Debug, Clone)]
86pub struct Syntax {
87    layers: Slab<LayerData>,
88    root: Layer,
89}
90
91impl Syntax {
92    pub fn new(
93        source: RopeSlice,
94        language: Language,
95        timeout: Duration,
96        loader: &impl LanguageLoader,
97    ) -> Result<Self, Error> {
98        let root_layer = LayerData {
99            parse_tree: None,
100            language,
101            flags: LayerUpdateFlags::default(),
102            ranges: vec![tree_sitter::Range::new(
103                tree_sitter::Point::ZERO,
104                tree_sitter::Point::MAX,
105                0,
106                u32::MAX,
107            )],
108            injections: Vec::new(),
109            parent: None,
110            locals: Locals::default(),
111        };
112        let mut layers = Slab::with_capacity(32);
113        let root = layers.insert(root_layer);
114        let mut syntax = Self {
115            root: Layer(root as u32),
116            layers,
117        };
118
119        syntax.update(source, timeout, &[], loader).map(|_| syntax)
120    }
121
122    pub fn layer(&self, layer: Layer) -> &LayerData {
123        &self.layers[layer.idx()]
124    }
125
126    fn layer_mut(&mut self, layer: Layer) -> &mut LayerData {
127        &mut self.layers[layer.idx()]
128    }
129
130    pub fn root(&self) -> Layer {
131        self.root
132    }
133
134    pub fn tree(&self) -> &Tree {
135        self.layer(self.root)
136            .tree()
137            .expect("`Syntax::new` would err if the root layer's tree could not be parsed")
138    }
139
140    #[inline]
141    pub fn tree_for_byte_range(&self, start: u32, end: u32) -> &Tree {
142        self.layer_and_tree_for_byte_range(start, end).1
143    }
144
145    /// Finds the smallest layer which has a parse tree and covers the given range.
146    pub(crate) fn layer_and_tree_for_byte_range(&self, start: u32, end: u32) -> (Layer, &Tree) {
147        let mut layer = self.layer_for_byte_range(start, end);
148        loop {
149            // NOTE: this loop is guaranteed to terminate because the root layer always has a
150            // tree.
151            if let Some(tree) = self.layer(layer).tree() {
152                return (layer, tree);
153            }
154            if let Some(parent) = self.layer(layer).parent {
155                layer = parent;
156            }
157        }
158    }
159
160    #[inline]
161    pub fn named_descendant_for_byte_range(&self, start: u32, end: u32) -> Option<Node<'_>> {
162        self.tree_for_byte_range(start, end)
163            .root_node()
164            .named_descendant_for_byte_range(start, end)
165    }
166
167    #[inline]
168    pub fn descendant_for_byte_range(&self, start: u32, end: u32) -> Option<Node<'_>> {
169        self.tree_for_byte_range(start, end)
170            .root_node()
171            .descendant_for_byte_range(start, end)
172    }
173
174    /// Finds the smallest injection layer that fully includes the range `start..=end`.
175    pub fn layer_for_byte_range(&self, start: u32, end: u32) -> Layer {
176        self.layers_for_byte_range(start, end)
177            .last()
178            .expect("always includes the root layer")
179    }
180
181    /// Returns an iterator of layers which **fully include** the byte range `start..=end`,
182    /// in decreasing order based on the size of each layer.
183    ///
184    /// The first layer is always the `root` layer.
185    pub fn layers_for_byte_range(&self, start: u32, end: u32) -> impl Iterator<Item = Layer> + '_ {
186        let mut parent_injection_layer = self.root;
187
188        std::iter::once(self.root).chain(std::iter::from_fn(move || {
189            let layer = &self.layers[parent_injection_layer.idx()];
190
191            let injection_at_start = layer.injection_at_byte_idx(start)?;
192            let injection_at_end = layer.injection_at_byte_idx(end)?;
193
194            (injection_at_start.layer == injection_at_end.layer).then(|| {
195                parent_injection_layer = injection_at_start.layer;
196
197                injection_at_start.layer
198            })
199        }))
200    }
201
202    pub fn walk(&self) -> TreeCursor<'_> {
203        TreeCursor::new(self)
204    }
205}
206
207#[derive(Debug, Clone)]
208pub struct Injection {
209    pub range: Range,
210    pub layer: Layer,
211    matched_node_range: Range,
212}
213
214#[derive(Debug, Clone)]
215pub struct LayerData {
216    pub language: Language,
217    parse_tree: Option<Tree>,
218    ranges: Vec<tree_sitter::Range>,
219    /// a list of **sorted** non-overlapping injection ranges. Note that
220    /// injection ranges are not relative to the start of this layer but the
221    /// start of the root layer
222    injections: Vec<Injection>,
223    /// internal flags used during parsing to track incremental invalidation
224    flags: LayerUpdateFlags,
225    parent: Option<Layer>,
226    locals: Locals,
227}
228
229/// This PartialEq implementation only checks if that
230/// two layers are theoretically identical (meaning they highlight the same text range with the same language).
231/// It does not check whether the layers have the same internal tree-sitter
232/// state.
233impl PartialEq for LayerData {
234    fn eq(&self, other: &Self) -> bool {
235        self.parent == other.parent
236            && self.language == other.language
237            && self.ranges == other.ranges
238    }
239}
240
241/// Hash implementation belongs to PartialEq implementation above.
242/// See its documentation for details.
243impl Hash for LayerData {
244    fn hash<H: Hasher>(&self, state: &mut H) {
245        self.parent.hash(state);
246        self.language.hash(state);
247        self.ranges.hash(state);
248    }
249}
250
251impl LayerData {
252    /// Returns the parsed `Tree` for this layer.
253    ///
254    /// This `Option` will always be `Some` when the `LanguageLoader` passed to `Syntax::new`
255    /// returns `Some` when passed the layer's language in `LanguageLoader::get_config`.
256    pub fn tree(&self) -> Option<&Tree> {
257        self.parse_tree.as_ref()
258    }
259
260    /// Returns the injection range **within this layers** that contains `idx`.
261    /// This function will not descend into nested injections
262    pub fn injection_at_byte_idx(&self, idx: u32) -> Option<&Injection> {
263        self.injections_at_byte_idx(idx)
264            .next()
265            .filter(|injection| injection.range.start <= idx)
266    }
267
268    /// Returns the injection ranges **within this layers** that contain
269    /// `idx` or start after idx. This function will not descend into nested
270    /// injections.
271    pub fn injections_at_byte_idx(&self, idx: u32) -> impl Iterator<Item = &Injection> {
272        let i = self
273            .injections
274            .partition_point(|range| range.range.end <= idx);
275        self.injections[i..].iter()
276    }
277}
278
279/// Represents the reason why syntax highlighting failed.
280#[derive(Debug, PartialEq, Eq)]
281pub enum Error {
282    Timeout,
283    ExceededMaximumSize,
284    InvalidRanges,
285    Unknown,
286    NoRootConfig,
287    IncompatibleGrammar(Language, IncompatibleGrammarError),
288}
289
290impl fmt::Display for Error {
291    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
292        match self {
293            Self::Timeout => f.write_str("configured timeout was exceeded"),
294            Self::ExceededMaximumSize => f.write_str("input text exceeds the maximum allowed size"),
295            Self::InvalidRanges => f.write_str("invalid ranges"),
296            Self::Unknown => f.write_str("an unknown error occurred"),
297            Self::NoRootConfig => f.write_str(
298                "`LanguageLoader::get_config` for the root layer language returned `None`",
299            ),
300            Self::IncompatibleGrammar(language, IncompatibleGrammarError { abi_version }) => {
301                write!(
302                    f,
303                    "failed to load grammar for language {language:?} with ABI version {abi_version}"
304                )
305            }
306        }
307    }
308}
309
310/// The maximum number of in-progress matches a TS cursor can consider at once.
311/// This is set to a constant in order to avoid performance problems for medium to large files. Set with `set_match_limit`.
312/// Using such a limit means that we lose valid captures, so there is fundamentally a tradeoff here.
313///
314///
315/// Old tree sitter versions used a limit of 32 by default until this limit was removed in version `0.19.5` (must now be set manually).
316/// However, this causes performance issues for medium to large files.
317/// In Helix, this problem caused tree-sitter motions to take multiple seconds to complete in medium-sized rust files (3k loc).
318///
319///
320/// Neovim also encountered this problem and reintroduced this limit after it was removed upstream
321/// (see <https://github.com/neovim/neovim/issues/14897> and <https://github.com/neovim/neovim/pull/14915>).
322/// The number used here is fundamentally a tradeoff between breaking some obscure edge cases and performance.
323///
324///
325/// Neovim chose 64 for this value somewhat arbitrarily (<https://github.com/neovim/neovim/pull/18397>).
326/// 64 is too low for some languages though. In particular, it breaks some highlighting for record fields in Erlang record definitions.
327/// This number can be increased if new syntax highlight breakages are found, as long as the performance penalty is not too high.
328pub const TREE_SITTER_MATCH_LIMIT: u32 = 256;
329
330// use 32 bit ranges since TS doesn't support files larger than 2GiB anyway
331// and it allows us to save a lot memory/improve cache efficiency
332type Range = std::ops::Range<u32>;
333
334#[cfg(test)]
335mod unit_tests {
336    use super::{Injection, Language, Layer, LayerData};
337    use crate::locals::Locals;
338    use crate::parse::LayerUpdateFlags;
339
340    fn make_injection(start: u32, end: u32) -> Injection {
341        Injection {
342            range: start..end,
343            layer: Layer(0),
344            matched_node_range: start..end,
345        }
346    }
347
348    fn layer_with_injections(injections: Vec<Injection>) -> LayerData {
349        LayerData {
350            language: Language(0),
351            parse_tree: None,
352            ranges: vec![],
353            injections,
354            flags: LayerUpdateFlags::default(),
355            parent: None,
356            locals: Locals::default(),
357        }
358    }
359
360    #[test]
361    fn injection_at_byte_idx_exclusive_end() {
362        let layer = layer_with_injections(vec![make_injection(5, 10)]);
363        // Byte 9 is the last byte of the range 5..10.
364        assert!(layer.injection_at_byte_idx(9).is_some());
365        // Byte 10 is the exclusive end and is not in the range.
366        assert!(layer.injection_at_byte_idx(10).is_none());
367    }
368
369    #[test]
370    fn injection_at_byte_idx_adjacent() {
371        // The boundary byte belongs to the second of two adjacent injections.
372        let layer = layer_with_injections(vec![make_injection(0, 10), make_injection(10, 20)]);
373        let inj = layer.injection_at_byte_idx(10).unwrap();
374        assert_eq!(inj.range, 10..20);
375    }
376}
tree_house/lib.rs

tree_house/
lib.rs
