cairo_lang_syntax/node/
mod.rs

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

cairo_lang_syntax/node/
mod.rs
