syntax/
algo.rs

1//! Collection of assorted algorithms for syntax trees.
2
3use itertools::Itertools;
4
5use crate::{
6    AstNode, Direction, NodeOrToken, SyntaxElement, SyntaxKind, SyntaxNode, SyntaxToken, TextRange,
7    TextSize, syntax_editor::Element,
8};
9
10/// Returns ancestors of the node at the offset, sorted by length. This should
11/// do the right thing at an edge, e.g. when searching for expressions at `{
12/// $0foo }` we will get the name reference instead of the whole block, which
13/// we would get if we just did `find_token_at_offset(...).flat_map(|t|
14/// t.parent().ancestors())`.
15pub fn ancestors_at_offset(
16    node: &SyntaxNode,
17    offset: TextSize,
18) -> impl Iterator<Item = SyntaxNode> {
19    node.token_at_offset(offset)
20        .map(|token| token.parent_ancestors())
21        .kmerge_by(|node1, node2| node1.text_range().len() < node2.text_range().len())
22}
23
24/// Finds a node of specific Ast type at offset. Note that this is slightly
25/// imprecise: if the cursor is strictly between two nodes of the desired type,
26/// as in
27///
28/// ```ignore
29/// struct Foo {}|struct Bar;
30/// ```
31///
32/// then the shorter node will be silently preferred.
33pub fn find_node_at_offset<N: AstNode>(syntax: &SyntaxNode, offset: TextSize) -> Option<N> {
34    ancestors_at_offset(syntax, offset).find_map(N::cast)
35}
36
37pub fn find_node_at_range<N: AstNode>(syntax: &SyntaxNode, range: TextRange) -> Option<N> {
38    syntax.covering_element(range).ancestors().find_map(N::cast)
39}
40
41/// Skip to next non `trivia` token
42pub fn skip_trivia_token(mut token: SyntaxToken, direction: Direction) -> Option<SyntaxToken> {
43    while token.kind().is_trivia() {
44        token = match direction {
45            Direction::Next => token.next_token()?,
46            Direction::Prev => token.prev_token()?,
47        }
48    }
49    Some(token)
50}
51/// Skip to next non `whitespace` token
52pub fn skip_whitespace_token(mut token: SyntaxToken, direction: Direction) -> Option<SyntaxToken> {
53    while token.kind() == SyntaxKind::WHITESPACE {
54        token = match direction {
55            Direction::Next => token.next_token()?,
56            Direction::Prev => token.prev_token()?,
57        }
58    }
59    Some(token)
60}
61
62/// Finds the first sibling in the given direction which is not `trivia`
63pub fn non_trivia_sibling(element: SyntaxElement, direction: Direction) -> Option<SyntaxElement> {
64    return match element {
65        NodeOrToken::Node(node) => node.siblings_with_tokens(direction).skip(1).find(not_trivia),
66        NodeOrToken::Token(token) => token.siblings_with_tokens(direction).skip(1).find(not_trivia),
67    };
68
69    fn not_trivia(element: &SyntaxElement) -> bool {
70        match element {
71            NodeOrToken::Node(_) => true,
72            NodeOrToken::Token(token) => !token.kind().is_trivia(),
73        }
74    }
75}
76
77pub fn least_common_ancestor(u: &SyntaxNode, v: &SyntaxNode) -> Option<SyntaxNode> {
78    if u == v {
79        return Some(u.clone());
80    }
81
82    let u_depth = u.ancestors().count();
83    let v_depth = v.ancestors().count();
84    let keep = u_depth.min(v_depth);
85
86    let u_candidates = u.ancestors().skip(u_depth - keep);
87    let v_candidates = v.ancestors().skip(v_depth - keep);
88    let (res, _) = u_candidates.zip(v_candidates).find(|(x, y)| x == y)?;
89    Some(res)
90}
91
92pub fn least_common_ancestor_element(u: impl Element, v: impl Element) -> Option<SyntaxNode> {
93    let u = u.syntax_element();
94    let v = v.syntax_element();
95    if u == v {
96        return match u {
97            NodeOrToken::Node(node) => Some(node),
98            NodeOrToken::Token(token) => token.parent(),
99        };
100    }
101
102    let u_depth = u.ancestors().count();
103    let v_depth = v.ancestors().count();
104    let keep = u_depth.min(v_depth);
105
106    let u_candidates = u.ancestors().skip(u_depth - keep);
107    let v_candidates = v.ancestors().skip(v_depth - keep);
108    let (res, _) = u_candidates.zip(v_candidates).find(|(x, y)| x == y)?;
109    Some(res)
110}
111
112pub fn neighbor<T: AstNode>(me: &T, direction: Direction) -> Option<T> {
113    me.syntax().siblings(direction).skip(1).find_map(T::cast)
114}
115
116pub fn has_errors(node: &SyntaxNode) -> bool {
117    node.children().any(|it| it.kind() == SyntaxKind::ERROR)
118}
119
120pub fn previous_non_trivia_token(e: impl Into<SyntaxElement>) -> Option<SyntaxToken> {
121    let mut token = match e.into() {
122        SyntaxElement::Node(n) => n.first_token()?,
123        SyntaxElement::Token(t) => t,
124    }
125    .prev_token();
126    while let Some(inner) = token {
127        if !inner.kind().is_trivia() {
128            return Some(inner);
129        } else {
130            token = inner.prev_token();
131        }
132    }
133    None
134}
syntax/algo.rs

syntax/
algo.rs
