cairo_lang_syntax/node/
mod.rs

1use core::hash::Hash;
2
3use cairo_lang_filesystem::db::FilesGroup;
4use cairo_lang_filesystem::ids::{FileId, SmolStrId};
5use cairo_lang_filesystem::span::{TextOffset, TextPosition, TextSpan, TextWidth};
6use cairo_lang_utils::{Intern, define_short_id, require};
7use salsa::Database;
8use vector_map::VecMap;
9
10use self::ast::TriviaGreen;
11use self::green::GreenNode;
12use self::ids::{GreenId, SyntaxStablePtrId};
13use self::kind::SyntaxKind;
14use self::stable_ptr::SyntaxStablePtr;
15use crate::node::db::SyntaxGroup;
16use crate::node::iter::{Preorder, WalkEvent};
17
18pub mod ast;
19pub mod db;
20pub mod element_list;
21pub mod green;
22pub mod helpers;
23pub mod ids;
24pub mod iter;
25pub mod key_fields;
26pub mod kind;
27pub mod stable_ptr;
28pub mod with_db;
29
30#[cfg(test)]
31mod ast_test;
32#[cfg(test)]
33mod test_utils;
34
35/// SyntaxNode. Untyped view of the syntax tree. Adds parent() and offset() capabilities.
36
37#[derive(Clone, Debug, Hash, PartialEq, Eq)]
38pub struct SyntaxNodeLongId<'a> {
39    green: GreenId<'a>,
40    /// Number of characters from the beginning of the file to the start of the span of this
41    /// syntax subtree.
42    offset: TextOffset,
43    parent: Option<SyntaxNode<'a>>,
44    stable_ptr: SyntaxStablePtrId<'a>,
45}
46define_short_id!(SyntaxNode, SyntaxNodeLongId<'db>);
47impl<'a> SyntaxNode<'a> {
48    pub fn new_root(db: &'a dyn Database, file_id: FileId<'a>, green: GreenId<'a>) -> Self {
49        Self::new_with_inner(
50            db,
51            green,
52            TextOffset::START,
53            None,
54            SyntaxStablePtr::Root(file_id, green).intern(db),
55        )
56    }
57
58    pub fn new_root_with_offset(
59        db: &'a dyn Database,
60        file_id: FileId<'a>,
61        green: GreenId<'a>,
62        initial_offset: Option<TextOffset>,
63    ) -> Self {
64        Self::new_with_inner(
65            db,
66            green,
67            initial_offset.unwrap_or_default(),
68            None,
69            SyntaxStablePtr::Root(file_id, green).intern(db),
70        )
71    }
72
73    pub fn new_with_inner(
74        db: &'a dyn Database,
75        green: GreenId<'a>,
76        offset: TextOffset,
77        parent: Option<SyntaxNode<'a>>,
78        stable_ptr: SyntaxStablePtrId<'a>,
79    ) -> Self {
80        SyntaxNodeLongId { green, offset, parent, stable_ptr }.intern(db)
81    }
82
83    pub fn offset(&self, db: &dyn Database) -> TextOffset {
84        self.long(db).offset
85    }
86    pub fn width(&self, db: &dyn Database) -> TextWidth {
87        self.green_node(db).width(db)
88    }
89    pub fn kind(&self, db: &dyn Database) -> SyntaxKind {
90        self.green_node(db).kind
91    }
92    pub fn span(&self, db: &dyn Database) -> TextSpan {
93        TextSpan::new_with_width(self.offset(db), self.width(db))
94    }
95    /// Returns the text of the token if this node is a token.
96    pub fn text(&self, db: &'a dyn Database) -> Option<SmolStrId<'a>> {
97        match &self.green_node(db).details {
98            green::GreenNodeDetails::Token(text) => Some(*text),
99            green::GreenNodeDetails::Node { .. } => None,
100        }
101    }
102
103    /// Returns the green node of the syntax node.
104    pub fn green_node(&self, db: &'a dyn Database) -> &'a GreenNode<'a> {
105        self.long(db).green.long(db)
106    }
107
108    /// Returns the span of the syntax node without trivia.
109    pub fn span_without_trivia(&self, db: &dyn Database) -> TextSpan {
110        let node = self.long(db);
111        let green_node = node.green.long(db);
112        let (leading, trailing) = both_trivia_width(db, green_node);
113        let start = node.offset.add_width(leading);
114        let end = node.offset.add_width(green_node.width(db)).sub_width(trailing);
115        TextSpan::new(start, end)
116    }
117    pub fn parent(&self, db: &'a dyn Database) -> Option<SyntaxNode<'a>> {
118        self.long(db).parent
119    }
120    pub fn stable_ptr(&self, db: &'a dyn Database) -> SyntaxStablePtrId<'a> {
121        self.long(db).stable_ptr
122    }
123
124    /// Gets the inner token from a terminal SyntaxNode. If the given node is not a terminal,
125    /// returns None.
126    pub fn get_terminal_token(&'a self, db: &'a dyn Database) -> Option<SyntaxNode<'a>> {
127        let green_node = self.green_node(db);
128        require(green_node.kind.is_terminal())?;
129        // At this point we know we should have a second child which is the token.
130        self.get_children(db).get(1).copied()
131    }
132
133    /// Gets the children syntax nodes of the current node.
134    pub fn get_children(&self, db: &'a dyn Database) -> &'a [SyntaxNode<'a>] {
135        db.get_children(*self)
136    }
137
138    /// Implementation of [SyntaxNode::get_children].
139    fn get_children_impl(&self, db: &'a dyn Database) -> Vec<SyntaxNode<'a>> {
140        let self_long_id = self.long(db);
141        let mut offset = self_long_id.offset;
142        let self_green = self_long_id.green.long(db);
143        let children = self_green.children();
144        let mut res: Vec<SyntaxNode<'_>> = Vec::with_capacity(children.len());
145        let mut key_map = VecMap::<_, usize>::new();
146        for green_id in children {
147            let green = green_id.long(db);
148            let width = green.width(db);
149            let kind = green.kind;
150            let rng = key_fields::key_fields_range(kind);
151            let key_fields: &'a [GreenId<'a>] = &green.children()[rng];
152            let key_count = key_map.entry((kind, key_fields)).or_insert(0);
153            let stable_ptr = SyntaxStablePtr::Child {
154                parent: self_long_id.stable_ptr,
155                kind,
156                key_fields: key_fields.into(),
157                index: *key_count,
158            }
159            .intern(db);
160            *key_count += 1;
161            // Create the SyntaxNode view for the child.
162            res.push(
163                SyntaxNodeLongId { green: *green_id, offset, parent: Some(*self), stable_ptr }
164                    .intern(db),
165            );
166
167            offset = offset.add_width(width);
168        }
169        res
170    }
171
172    /// Returns the start of the span of the syntax node without trivia.
173    pub fn span_start_without_trivia(&self, db: &dyn Database) -> TextOffset {
174        let node = self.long(db);
175        let green_node = node.green.long(db);
176        let leading = leading_trivia_width(db, green_node);
177        node.offset.add_width(leading)
178    }
179
180    /// Returns the end of the span of the syntax node without trivia.
181    pub fn span_end_without_trivia(&self, db: &dyn Database) -> TextOffset {
182        let node = self.long(db);
183        let green_node = node.green.long(db);
184        let trailing = trailing_trivia_width(db, green_node);
185        node.offset.add_width(green_node.width(db)).sub_width(trailing)
186    }
187
188    /// Lookups a syntax node using an offset.
189    pub fn lookup_offset(&self, db: &'a dyn Database, offset: TextOffset) -> SyntaxNode<'a> {
190        for child in self.get_children(db).iter() {
191            if child.offset(db).add_width(child.width(db)) > offset {
192                return child.lookup_offset(db, offset);
193            }
194        }
195        *self
196    }
197
198    /// Lookups a syntax node using a position.
199    pub fn lookup_position(&self, db: &'a dyn Database, position: TextPosition) -> SyntaxNode<'a> {
200        match position.offset_in_file(db, self.stable_ptr(db).file_id(db)) {
201            Some(offset) => self.lookup_offset(db, offset),
202            None => *self,
203        }
204    }
205
206    /// Returns all the text under the syntax node.
207    pub fn get_text(&self, db: &'a dyn Database) -> &'a str {
208        // A `None` return from reading the file content is only expected in the case of an IO
209        // error. Since a SyntaxNode exists and is being processed, we should have already
210        // successfully accessed this file earlier, therefore it should never fail.
211        let file_content =
212            db.file_content(self.stable_ptr(db).file_id(db)).expect("Failed to read file content");
213
214        self.span(db).take(file_content)
215    }
216
217    /// Returns all the text under the syntax node.
218    /// It traverses all the syntax tree of the node, but ignores functions and modules.
219    /// We ignore those, because if there's some inner functions or modules, we don't want to get
220    /// raw text of them. Comments inside them refer themselves directly, not this SyntaxNode.
221    pub fn get_text_without_inner_commentable_children(&self, db: &dyn Database) -> String {
222        let mut buffer = String::new();
223
224        match &self.green_node(db).details {
225            green::GreenNodeDetails::Token(text) => buffer.push_str(text.long(db)),
226            green::GreenNodeDetails::Node { .. } => {
227                for child in self.get_children(db).iter() {
228                    let kind = child.kind(db);
229
230                    // Checks all the items that the inner comment can be bubbled to (implementation
231                    // function is also a FunctionWithBody).
232                    if !matches!(
233                        kind,
234                        SyntaxKind::FunctionWithBody
235                            | SyntaxKind::ItemModule
236                            | SyntaxKind::TraitItemFunction
237                    ) {
238                        buffer.push_str(&SyntaxNode::get_text_without_inner_commentable_children(
239                            child, db,
240                        ));
241                    }
242                }
243            }
244        }
245        buffer
246    }
247
248    /// Returns all the text of the item without comments trivia.
249    /// It traverses all the syntax tree of the node.
250    pub fn get_text_without_all_comment_trivia(&self, db: &dyn Database) -> String {
251        let mut buffer = String::new();
252
253        match &self.green_node(db).details {
254            green::GreenNodeDetails::Token(text) => buffer.push_str(text.long(db)),
255            green::GreenNodeDetails::Node { .. } => {
256                for child in self.get_children(db).iter() {
257                    if let Some(trivia) = ast::Trivia::cast(db, *child) {
258                        trivia.elements(db).for_each(|element| {
259                            if !matches!(
260                                element,
261                                ast::Trivium::SingleLineComment(_)
262                                    | ast::Trivium::SingleLineDocComment(_)
263                                    | ast::Trivium::SingleLineInnerComment(_)
264                            ) {
265                                buffer.push_str(
266                                    &element
267                                        .as_syntax_node()
268                                        .get_text_without_all_comment_trivia(db),
269                                );
270                            }
271                        });
272                    } else {
273                        buffer
274                            .push_str(&SyntaxNode::get_text_without_all_comment_trivia(child, db));
275                    }
276                }
277            }
278        }
279        buffer
280    }
281
282    /// Returns all the text under the syntax node, without the outmost trivia (the leading trivia
283    /// of the first token and the trailing trivia of the last token).
284    ///
285    /// Note that this traverses the syntax tree, and generates a new string, so use responsibly.
286    pub fn get_text_without_trivia(self, db: &'a dyn Database) -> SmolStrId<'a> {
287        let file_content =
288            db.file_content(self.stable_ptr(db).file_id(db)).expect("Failed to read file content");
289        SmolStrId::from(db, self.span_without_trivia(db).take(file_content))
290    }
291
292    /// Returns the text under the syntax node, according to the given span.
293    ///
294    /// `span` is assumed to be contained within the span of self.
295    ///
296    /// Note that this traverses the syntax tree, and generates a new string, so use responsibly.
297    pub fn get_text_of_span(self, db: &'a dyn Database, span: TextSpan) -> &'a str {
298        assert!(self.span(db).contains(span));
299        let file_content =
300            db.file_content(self.stable_ptr(db).file_id(db)).expect("Failed to read file content");
301        span.take(file_content)
302    }
303
304    /// Traverse the subtree rooted at the current node (including the current node) in preorder.
305    ///
306    /// This is a shortcut for [`Self::preorder`] paired with filtering for [`WalkEvent::Enter`]
307    /// events only.
308    pub fn descendants(&self, db: &'a dyn Database) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
309        self.preorder(db).filter_map(|event| match event {
310            WalkEvent::Enter(node) => Some(node),
311            WalkEvent::Leave(_) => None,
312        })
313    }
314
315    /// Traverse the subtree rooted at the current node (including the current node) in preorder,
316    /// excluding tokens.
317    pub fn preorder(&self, db: &'a dyn Database) -> Preorder<'a> {
318        Preorder::new(*self, db)
319    }
320
321    /// Gets all the leaves of the SyntaxTree, where the self node is the root of a tree.
322    pub fn tokens(&self, db: &'a dyn Database) -> impl Iterator<Item = Self> + 'a {
323        self.preorder(db).filter_map(|event| match event {
324            WalkEvent::Enter(node) if node.green_node(db).kind.is_terminal() => Some(node),
325            _ => None,
326        })
327    }
328
329    /// Mirror of [`TypedSyntaxNode::cast`].
330    pub fn cast<T: TypedSyntaxNode<'a>>(self, db: &'a dyn Database) -> Option<T> {
331        T::cast(db, self)
332    }
333
334    /// Creates an iterator that yields ancestors of this syntax node.
335    pub fn ancestors(&self, db: &'a dyn Database) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
336        // We aren't reusing `ancestors_with_self` here to avoid cloning this node.
337        std::iter::successors(self.parent(db), |n| n.parent(db))
338    }
339
340    /// Creates an iterator that yields this syntax node and walks up its ancestors.
341    pub fn ancestors_with_self(
342        &self,
343        db: &'a dyn Database,
344    ) -> impl Iterator<Item = SyntaxNode<'a>> + 'a {
345        std::iter::successors(Some(*self), |n| n.parent(db))
346    }
347
348    /// Checks whether this syntax node is strictly above the given syntax node in the syntax tree.
349    pub fn is_ancestor(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
350        node.ancestors(db).any(|n| n == *self)
351    }
352
353    /// Checks whether this syntax node is strictly under the given syntax node in the syntax tree.
354    pub fn is_descendant(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
355        node.is_ancestor(db, self)
356    }
357
358    /// Checks whether this syntax node is or is above the given syntax node in the syntax tree.
359    pub fn is_ancestor_or_self(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
360        node.ancestors_with_self(db).any(|n| n == *self)
361    }
362
363    /// Checks whether this syntax node is or is under the given syntax node in the syntax tree.
364    pub fn is_descendant_or_self(&self, db: &dyn Database, node: &SyntaxNode<'_>) -> bool {
365        node.is_ancestor_or_self(db, self)
366    }
367
368    /// Finds the first ancestor of a given kind.
369    pub fn ancestor_of_kind(
370        &self,
371        db: &'a dyn Database,
372        kind: SyntaxKind,
373    ) -> Option<SyntaxNode<'a>> {
374        self.ancestors(db).find(|node| node.kind(db) == kind)
375    }
376
377    /// Finds the first ancestor of a given kind and returns it in typed form.
378    pub fn ancestor_of_type<T: TypedSyntaxNode<'a>>(&self, db: &'a dyn Database) -> Option<T> {
379        self.ancestors(db).find_map(|node| T::cast(db, node))
380    }
381
382    /// Finds the parent of a given kind.
383    pub fn parent_of_kind(&self, db: &'a dyn Database, kind: SyntaxKind) -> Option<SyntaxNode<'a>> {
384        self.parent(db).filter(|node| node.kind(db) == kind)
385    }
386
387    /// Finds the parent of a given kind and returns it in typed form.
388    pub fn parent_of_type<T: TypedSyntaxNode<'a>>(&self, db: &'a dyn Database) -> Option<T> {
389        self.parent(db).and_then(|node| T::cast(db, node))
390    }
391
392    /// Finds the first parent of one of the kinds.
393    pub fn ancestor_of_kinds(
394        &self,
395        db: &'a dyn Database,
396        kinds: &[SyntaxKind],
397    ) -> Option<SyntaxNode<'a>> {
398        self.ancestors(db).find(|node| kinds.contains(&node.kind(db)))
399    }
400
401    /// Gets the kind of the given node's parent if it exists.
402    pub fn parent_kind(&self, db: &dyn Database) -> Option<SyntaxKind> {
403        Some(self.parent(db)?.kind(db))
404    }
405
406    /// Gets the kind of the given node's grandparent if it exists.
407    pub fn grandparent_kind(&self, db: &dyn Database) -> Option<SyntaxKind> {
408        Some(self.parent(db)?.parent(db)?.kind(db))
409    }
410
411    /// Gets the kind of the given node's grandgrandparent if it exists.
412    pub fn grandgrandparent_kind(&self, db: &dyn Database) -> Option<SyntaxKind> {
413        Some(self.parent(db)?.parent(db)?.parent(db)?.kind(db))
414    }
415}
416
417/// Trait for the typed view of the syntax tree. All the internal node implementations are under
418/// the ast module.
419pub trait TypedSyntaxNode<'a>: Sized {
420    /// The relevant SyntaxKind. None for enums.
421    const OPTIONAL_KIND: Option<SyntaxKind>;
422    type StablePtr: TypedStablePtr<'a>;
423    type Green;
424    fn missing(db: &'a dyn Database) -> Self::Green;
425    fn from_syntax_node(db: &'a dyn Database, node: SyntaxNode<'a>) -> Self;
426    fn cast(db: &'a dyn Database, node: SyntaxNode<'a>) -> Option<Self>;
427    fn as_syntax_node(&self) -> SyntaxNode<'a>;
428    fn stable_ptr(&self, db: &'a dyn Database) -> Self::StablePtr;
429}
430
431pub trait Token<'a>: TypedSyntaxNode<'a> {
432    fn new_green(db: &'a dyn Database, text: SmolStrId<'a>) -> Self::Green;
433    fn text(&self, db: &'a dyn Database) -> SmolStrId<'a>;
434}
435
436pub trait Terminal<'a>: TypedSyntaxNode<'a> {
437    const KIND: SyntaxKind;
438    type TokenType: Token<'a>;
439    fn new_green(
440        db: &'a dyn Database,
441        leading_trivia: TriviaGreen<'a>,
442        token: <<Self as Terminal<'a>>::TokenType as TypedSyntaxNode<'a>>::Green,
443        trailing_trivia: TriviaGreen<'a>,
444    ) -> <Self as TypedSyntaxNode<'a>>::Green;
445    /// Returns the text of the token of this terminal (excluding the trivia).
446    fn text(&self, db: &'a dyn Database) -> SmolStrId<'a>;
447    /// Casts a syntax node to this terminal type's token and then walks up to return the terminal.
448    fn cast_token(db: &'a dyn Database, node: SyntaxNode<'a>) -> Option<Self> {
449        if node.kind(db) == Self::TokenType::OPTIONAL_KIND? {
450            Some(Self::from_syntax_node(db, node.parent(db)?))
451        } else {
452            None
453        }
454    }
455}
456
457/// Trait for stable pointers to syntax nodes.
458pub trait TypedStablePtr<'a> {
459    type SyntaxNode: TypedSyntaxNode<'a>;
460    /// Returns the syntax node pointed to by this stable pointer.
461    fn lookup(&self, db: &'a dyn Database) -> Self::SyntaxNode;
462    /// Returns the untyped stable pointer.
463    fn untyped(self) -> SyntaxStablePtrId<'a>;
464}
465
466/// Returns the width of the leading trivia of the given green node.
467fn leading_trivia_width<'a>(db: &'a dyn Database, green: &GreenNode<'a>) -> TextWidth {
468    match &green.details {
469        green::GreenNodeDetails::Token(_) => TextWidth::default(),
470        green::GreenNodeDetails::Node { children, width } => {
471            if *width == TextWidth::default() {
472                return TextWidth::default();
473            }
474            if green.kind.is_terminal() {
475                return children[0].long(db).width(db);
476            }
477            let non_empty = find_non_empty_child(db, &mut children.iter())
478                .expect("Parent width non-empty - one of the children should be non-empty");
479            leading_trivia_width(db, non_empty)
480        }
481    }
482}
483
484/// Returns the width of the trailing trivia of the given green node.
485fn trailing_trivia_width<'a>(db: &'a dyn Database, green: &GreenNode<'a>) -> TextWidth {
486    match &green.details {
487        green::GreenNodeDetails::Token(_) => TextWidth::default(),
488        green::GreenNodeDetails::Node { children, width } => {
489            if *width == TextWidth::default() {
490                return TextWidth::default();
491            }
492            if green.kind.is_terminal() {
493                return children[2].long(db).width(db);
494            }
495            let non_empty = find_non_empty_child(db, &mut children.iter().rev())
496                .expect("Parent width non-empty - one of the children should be non-empty");
497            trailing_trivia_width(db, non_empty)
498        }
499    }
500}
501
502/// Returns the width of the leading and trailing trivia of the given green node.
503fn both_trivia_width<'a>(db: &'a dyn Database, green: &GreenNode<'a>) -> (TextWidth, TextWidth) {
504    match &green.details {
505        green::GreenNodeDetails::Token(_) => (TextWidth::default(), TextWidth::default()),
506        green::GreenNodeDetails::Node { children, width } => {
507            if *width == TextWidth::default() {
508                return (TextWidth::default(), TextWidth::default());
509            }
510            if green.kind.is_terminal() {
511                return (children[0].long(db).width(db), children[2].long(db).width(db));
512            }
513            let mut iter = children.iter();
514            let first_non_empty = find_non_empty_child(db, &mut iter)
515                .expect("Parent width non-empty - one of the children should be non-empty");
516            if let Some(last_non_empty) = find_non_empty_child(db, &mut iter.rev()) {
517                (
518                    leading_trivia_width(db, first_non_empty),
519                    trailing_trivia_width(db, last_non_empty),
520                )
521            } else {
522                both_trivia_width(db, first_non_empty)
523            }
524        }
525    }
526}
527
528/// Finds the first non-empty child in the given iterator.
529fn find_non_empty_child<'a>(
530    db: &'a dyn Database,
531    child_iter: &mut impl Iterator<Item = &'a GreenId<'a>>,
532) -> Option<&'a GreenNode<'a>> {
533    child_iter.find_map(|child| {
534        let child = child.long(db);
535        (child.width(db) != TextWidth::default()).then_some(child)
536    })
537}
cairo_lang_syntax/node/mod.rs

cairo_lang_syntax/node/
mod.rs
