cairo_lang_syntax/node/
mod.rs

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

cairo_lang_syntax/node/
mod.rs
