biome_rowan/ast/
mod.rs

1//! AST definitions for converting untyped syntax nodes into typed AST nodes.
2//!
3//! Every field of every AST node is optional, this is to allow the parser to recover
4//! from any error and produce an ast from any source code. If you don't want to account for
5//! optionals for everything, you can use ...
6
7use biome_text_size::TextRange;
8#[cfg(feature = "serde")]
9use serde::Serialize;
10use std::error::Error;
11use std::fmt::{self, Debug, Display, Formatter};
12use std::iter::FusedIterator;
13use std::marker::PhantomData;
14
15mod batch;
16mod mutation;
17
18use crate::syntax::{SyntaxSlot, SyntaxSlots};
19use crate::{
20    Language, RawSyntaxKind, SyntaxKind, SyntaxList, SyntaxNode, SyntaxToken, SyntaxTriviaPiece,
21};
22pub use batch::*;
23pub use mutation::{AstNodeExt, AstNodeListExt, AstSeparatedListExt};
24
25/// Represents a set of [SyntaxKind] as a bitfield, with each bit representing
26/// whether the corresponding [RawSyntaxKind] value is contained in the set
27///
28/// This is similar to the `TokenSet` struct in `biome_js_parser`, with the
29/// bitfield here being twice as large as it needs to cover all nodes as well
30/// as all token kinds
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub struct SyntaxKindSet<L: Language>([u128; 4], PhantomData<L>);
33
34impl<L> SyntaxKindSet<L>
35where
36    L: Language,
37{
38    /// Create a new [SyntaxKindSet] containing only the provided [SyntaxKind]
39    pub fn of(kind: L::Kind) -> Self {
40        Self::from_raw(kind.to_raw())
41    }
42
43    /// Create a new [SyntaxKindSet] containing only the provided [RawSyntaxKind]
44    ///
45    /// Unlike `SyntaxKindSet::of` this function can be evaluated in constants,
46    /// and will result in a compile-time error if the value overflows:
47    ///
48    /// ```compile_fail
49    /// # use biome_rowan::{SyntaxKindSet, RawSyntaxKind, raw_language::RawLanguage};
50    /// const EXAMPLE: SyntaxKindSet<RawLanguage> =
51    ///     SyntaxKindSet::<RawLanguage>::from_raw(RawSyntaxKind(512));
52    /// # println!("{EXAMPLE:?}"); // The constant must be used to be evaluated
53    /// ```
54    pub const fn from_raw(kind: RawSyntaxKind) -> Self {
55        let RawSyntaxKind(kind) = kind;
56
57        let index = kind as usize / u128::BITS as usize;
58        let shift = kind % u128::BITS as u16;
59        let mask = 1 << shift;
60
61        let mut bits = [0; 4];
62        bits[index] = mask;
63
64        Self(bits, PhantomData)
65    }
66
67    /// Returns the union of the two sets `self` and `other`
68    pub const fn union(self, other: Self) -> Self {
69        Self(
70            [
71                self.0[0] | other.0[0],
72                self.0[1] | other.0[1],
73                self.0[2] | other.0[2],
74                self.0[3] | other.0[3],
75            ],
76            PhantomData,
77        )
78    }
79
80    /// Returns true if `kind` is contained in this set
81    pub fn matches(self, kind: L::Kind) -> bool {
82        let RawSyntaxKind(kind) = kind.to_raw();
83
84        let index = kind as usize / u128::BITS as usize;
85        let shift = kind % u128::BITS as u16;
86        let mask = 1 << shift;
87
88        self.0[index] & mask != 0
89    }
90
91    /// Returns an iterator over all the [SyntaxKind] contained in this set
92    pub fn iter(self) -> impl Iterator<Item = L::Kind> {
93        self.0.into_iter().enumerate().flat_map(|(index, item)| {
94            let index = index as u16 * u128::BITS as u16;
95            (0..u128::BITS).filter_map(move |bit| {
96                if (item & (1 << bit)) != 0 {
97                    let raw = index + bit as u16;
98                    let raw = RawSyntaxKind(raw);
99                    Some(<L::Kind as SyntaxKind>::from_raw(raw))
100                } else {
101                    None
102                }
103            })
104        })
105    }
106}
107
108/// The main trait to go from untyped `SyntaxNode` to a typed ast. The
109/// conversion itself has zero runtime cost: ast and syntax nodes have exactly
110/// the same representation: a pointer to the tree root and a pointer to the
111/// node itself.
112///
113/// The only exception to this is for Dynamic nodes, which allow the fields
114/// of the AstNode to be mapped to any slot of the SyntaxNode using an additional
115/// `slot_map`. This must get built every time the untyped syntax node is
116/// converted into the typed ast node, and is determined by the order of fields
117/// in the original grammar. Even still, this cost is relatively low and should
118/// not be considered prohibitive, as the only work done is checking
119/// [AstNode::can_cast] for each of the children to their respective slots.
120pub trait AstNode: Clone {
121    type Language: Language;
122
123    const KIND_SET: SyntaxKindSet<Self::Language>;
124
125    /// Returns `true` if a node with the given kind can be cased to this AST node.
126    fn can_cast(kind: <Self::Language as Language>::Kind) -> bool;
127
128    /// Tries to cast the passed syntax node to this AST node.
129    ///
130    /// # Returns
131    ///
132    /// [None] if the passed node is of a different kind. [Some] otherwise.
133    fn cast(syntax: SyntaxNode<Self::Language>) -> Option<Self>
134    where
135        Self: Sized;
136
137    /// Takes a reference of a syntax node and tries to cast it to this AST node.
138    ///
139    /// Only creates a clone of the syntax node if casting the node is possible.
140    fn cast_ref(syntax: &SyntaxNode<Self::Language>) -> Option<Self>
141    where
142        Self: Sized,
143    {
144        if Self::can_cast(syntax.kind()) {
145            Self::cast(syntax.clone())
146        } else {
147            None
148        }
149    }
150
151    /// Tries to cast the passed syntax node to this AST node.
152    ///
153    /// # Returns
154    /// * [Ok] if the passed node can be cast into this [AstNode]
155    /// * [Err(syntax)](Err) If the node is of another kind.
156    ///
157    /// # Examples
158    ///
159    /// ```
160    /// # use biome_rowan::AstNode;
161    /// # use biome_rowan::raw_language::{LiteralExpression, RawLanguageKind, RawLanguageRoot, RawSyntaxTreeBuilder};
162    ///
163    /// let mut builder = RawSyntaxTreeBuilder::new();
164    ///
165    /// builder.start_node(RawLanguageKind::ROOT);
166    /// builder.start_node(RawLanguageKind::LITERAL_EXPRESSION);
167    /// builder.token(RawLanguageKind::STRING_TOKEN, "'abcd'");
168    /// builder.finish_node();
169    /// builder.finish_node();
170    ///
171    /// let root_syntax = builder.finish();
172    /// let root = RawLanguageRoot::cast_ref(&root_syntax).expect("Root to be a raw language root");
173    ///
174    /// // Returns `OK` because syntax is a `RawLanguageRoot`
175    /// assert_eq!(RawLanguageRoot::try_cast(root.syntax().clone()), Ok(root.clone()));
176    /// // Returns `Err` with the syntax node passed to `try_cast` because `root` isn't a `LiteralExpression`
177    /// assert_eq!(LiteralExpression::try_cast(root.syntax().clone()), Err(root_syntax));
178    /// ```
179    fn try_cast(syntax: SyntaxNode<Self::Language>) -> Result<Self, SyntaxNode<Self::Language>> {
180        if Self::can_cast(syntax.kind()) {
181            Ok(Self::unwrap_cast(syntax))
182        } else {
183            Err(syntax)
184        }
185    }
186
187    /// Returns the underlying syntax node.
188    fn syntax(&self) -> &SyntaxNode<Self::Language>;
189
190    /// Returns the underlying syntax node.
191    fn into_syntax(self) -> SyntaxNode<Self::Language>;
192
193    /// Cast this node to this AST node
194    ///
195    /// # Panics
196    /// Panics if the underlying node cannot be cast to this AST node
197    fn unwrap_cast(syntax: SyntaxNode<Self::Language>) -> Self
198    where
199        Self: Sized,
200    {
201        let kind = syntax.kind();
202        Self::cast(syntax).unwrap_or_else(|| {
203            panic!(
204                "Tried to cast node with kind {:?} as `{:?}` but was unable to cast",
205                kind,
206                std::any::type_name::<Self>()
207            )
208        })
209    }
210
211    /// Returns the string representation of this node without the leading and trailing trivia
212    fn text(&self) -> std::string::String {
213        self.syntax().text_trimmed().to_string()
214    }
215
216    fn range(&self) -> TextRange {
217        self.syntax().text_trimmed_range()
218    }
219
220    fn clone_subtree(&self) -> Self
221    where
222        Self: Sized,
223    {
224        Self::cast(self.syntax().clone_subtree()).unwrap()
225    }
226
227    fn parent<T: AstNode<Language = Self::Language>>(&self) -> Option<T> {
228        self.syntax().parent().and_then(T::cast)
229    }
230
231    /// Return a new version of this node with the leading trivia of its first token replaced with `trivia`.
232    fn with_leading_trivia_pieces<I>(self, trivia: I) -> Option<Self>
233    where
234        I: IntoIterator<Item = SyntaxTriviaPiece<Self::Language>>,
235        I::IntoIter: ExactSizeIterator,
236    {
237        Self::cast(self.into_syntax().with_leading_trivia_pieces(trivia)?)
238    }
239
240    /// Return a new version of this node with the trailing trivia of its last token replaced with `trivia`.
241    fn with_trailing_trivia_pieces<I>(self, trivia: I) -> Option<Self>
242    where
243        I: IntoIterator<Item = SyntaxTriviaPiece<Self::Language>>,
244        I::IntoIter: ExactSizeIterator,
245    {
246        Self::cast(self.into_syntax().with_trailing_trivia_pieces(trivia)?)
247    }
248
249    // Return a new version of this node with `trivia` prepended to the leading trivia of the first token.
250    fn prepend_trivia_pieces<I>(self, trivia: I) -> Option<Self>
251    where
252        I: IntoIterator<Item = SyntaxTriviaPiece<Self::Language>>,
253        I::IntoIter: ExactSizeIterator,
254    {
255        Self::cast(self.into_syntax().prepend_trivia_pieces(trivia)?)
256    }
257
258    // Return a new version of this node with `trivia` appended to the trailing trivia of the last token.
259    fn append_trivia_pieces<I>(self, trivia: I) -> Option<Self>
260    where
261        I: IntoIterator<Item = SyntaxTriviaPiece<Self::Language>>,
262        I::IntoIter: ExactSizeIterator,
263    {
264        Self::cast(self.into_syntax().append_trivia_pieces(trivia)?)
265    }
266
267    /// Return a new version of this node without leading and trailing newlines and whitespaces.
268    fn trim_trivia(self) -> Option<Self> {
269        Self::cast(
270            self.into_syntax()
271                .trim_leading_trivia()?
272                .trim_trailing_trivia()?,
273        )
274    }
275
276    /// Return a new version of this node without leading newlines and whitespaces.
277    fn trim_leading_trivia(self) -> Option<Self> {
278        Self::cast(self.into_syntax().trim_leading_trivia()?)
279    }
280
281    /// Return a new version of this node without trailing newlines and whitespaces.
282    fn trim_trailing_trivia(self) -> Option<Self> {
283        Self::cast(self.into_syntax().trim_trailing_trivia()?)
284    }
285}
286
287/// An AstNode that supports dynamic ordering of the fields it contains uses a
288/// `slot_map` to map the _declared_ order of fields to the _concrete_ order
289/// as parsed from the source content. Implementing this trait lets consumers
290///
291pub trait AstNodeSlotMap<const N: usize> {
292    /// Return the internal slot_map that was built when constructed from the
293    /// underlying [SyntaxNode].
294    fn slot_map(&self) -> &[u8; N];
295
296    /// Invert and sort the `slot_map` for the [AstNode] to return a mapping of
297    /// _concrete_ field ordering from the source to the _declared_ ordering of
298    /// the [AstNode].
299    ///
300    /// Note that the _entire_ slot map is inverted and returned, including
301    /// both the ordered and the unordered fields. Ordered fields will have
302    /// their slot positions fixed in both the original and the inverted slot
303    /// maps, since they can't be moved. Ordered fields also act as boundary
304    /// points for unordered fields, meaning the concrete order will never
305    /// allow the concrete slot of an unordered field to appear on the opposite
306    /// side of an ordered field, even if the field is empty, and the ordered
307    /// fields will _always_ have the same slot in both maps.
308    ///
309    /// Example: Given a grammar like:
310    ///   MultiplyVectorsNode =
311    ///     (Color
312    ///     || Number
313    ///     || String)
314    ///     'x'
315    ///     (Color
316    ///     || Number
317    ///     || String)
318    /// There are two sets of unordered fields here (the groups combined with
319    /// `||` operators). Each contains three fields, and then there is a single
320    /// ordered field between them, the `x` token. This Node declares a
321    /// `slot_map` with 7 indices. The first three can be mapped in any order,
322    /// and the last three can be mapped in any order, but the `x` token will
323    /// _always_ occupy the fourth slot (zero-based index 3).
324    ///
325    /// Now, given an input like `10 "hello" #fff x "bye" #000 20`, the
326    /// constructed [AstNode]'s slot_map would look like
327    /// `[2, 0, 1, 3, 6, 4, 5]`. The first `Color` field, declared as index 0,
328    /// appears at the 2nd index in the concrete source, so the value at index
329    /// 0 is 2, and so on for the rest of the fields.
330    ///
331    /// The inversion of this slot map, then, is `[1, 2, 0, 3, 5, 6, 4]`. To
332    /// compare these, think: the value 0 in the original `slot_map` appeared
333    /// at index 1, so index 0 in the inverted map has the _value_ 1, then
334    /// apply that for of the slots. As you can see `3` is still in the same
335    /// position, because it is an ordered field.
336    ///
337    /// ## Optional Fields
338    ///
339    /// It's also possible for unordered fields to be _optional_, meaning they
340    /// are not present in the concrete source. In this case, the sentinel
341    /// value of `255` ([`std::u8::MAX`]) is placed in the slot map. When
342    /// inverting the map, if a slot index cannot be found in the map, it is
343    /// preserved as the same sentinel value in the inverted map.
344    ///
345    /// Using the same grammar as before, the input `10 x #000` is also valid,
346    /// but is missing many of the optional fields. The `slot_map` for this
347    /// node would include sentinel values for all of the missing fields, like:
348    /// `[255, 0, 255, 3, 4, 255, 255]`. Inverting this map would then yield:
349    /// `[1, 255, 255, 3, 4, 255, 255]`. Each declared slot is still
350    /// represented in the inverted map, but only the fields that exist in the
351    /// concrete source have usable values.
352    fn concrete_order_slot_map(&self) -> [u8; N] {
353        let mut inverted = [u8::MAX; N];
354        for (declared_slot, concrete_slot) in self.slot_map().iter().enumerate() {
355            if *concrete_slot != u8::MAX {
356                inverted[*concrete_slot as usize] = declared_slot as u8;
357            }
358        }
359
360        inverted
361    }
362}
363
364pub trait SyntaxNodeCast<L: Language> {
365    /// Tries to cast the current syntax node to specified AST node.
366    ///
367    /// # Returns
368    ///
369    /// [None] if the current node is of a different kind. [Some] otherwise.
370    fn cast<T: AstNode<Language = L>>(self) -> Option<T>;
371}
372
373impl<L: Language> SyntaxNodeCast<L> for SyntaxNode<L> {
374    fn cast<T: AstNode<Language = L>>(self) -> Option<T> {
375        T::cast(self)
376    }
377}
378
379/// List of homogenous nodes
380pub trait AstNodeList {
381    type Language: Language;
382    type Node: AstNode<Language = Self::Language>;
383
384    /// Returns the underlying syntax list
385    fn syntax_list(&self) -> &SyntaxList<Self::Language>;
386
387    /// Returns the underlying syntax list
388    fn into_syntax_list(self) -> SyntaxList<Self::Language>;
389
390    fn iter(&self) -> AstNodeListIterator<Self::Language, Self::Node> {
391        AstNodeListIterator {
392            inner: self.syntax_list().iter(),
393            ph: PhantomData,
394        }
395    }
396
397    #[inline]
398    fn len(&self) -> usize {
399        self.syntax_list().len()
400    }
401
402    /// Returns the first node from this list or None
403    #[inline]
404    fn first(&self) -> Option<Self::Node> {
405        self.iter().next()
406    }
407
408    /// Returns the last node from this list or None
409    fn last(&self) -> Option<Self::Node> {
410        self.iter().last()
411    }
412
413    #[inline]
414    fn is_empty(&self) -> bool {
415        self.syntax_list().is_empty()
416    }
417}
418
419#[derive(Debug, Clone)]
420pub struct AstNodeListIterator<L, N>
421where
422    L: Language,
423{
424    inner: SyntaxSlots<L>,
425    ph: PhantomData<N>,
426}
427
428impl<L: Language, N: AstNode<Language = L>> AstNodeListIterator<L, N> {
429    fn slot_to_node(slot: &SyntaxSlot<L>) -> N {
430        match slot {
431            SyntaxSlot::Empty { .. } => panic!("Node isn't permitted to contain empty slots"),
432            SyntaxSlot::Node(node) => N::unwrap_cast(node.clone()),
433            SyntaxSlot::Token(token) => panic!(
434                "Expected node of type `{:?}` but found token `{:?}` instead.",
435                std::any::type_name::<N>(),
436                token
437            ),
438        }
439    }
440}
441
442impl<L: Language, N: AstNode<Language = L>> Iterator for AstNodeListIterator<L, N> {
443    type Item = N;
444
445    fn next(&mut self) -> Option<Self::Item> {
446        Some(Self::slot_to_node(&self.inner.next()?))
447    }
448
449    fn size_hint(&self) -> (usize, Option<usize>) {
450        self.inner.size_hint()
451    }
452
453    fn last(self) -> Option<Self::Item>
454    where
455        Self: Sized,
456    {
457        Some(Self::slot_to_node(&self.inner.last()?))
458    }
459
460    fn nth(&mut self, n: usize) -> Option<Self::Item> {
461        Some(Self::slot_to_node(&self.inner.nth(n)?))
462    }
463}
464
465impl<L: Language, N: AstNode<Language = L>> ExactSizeIterator for AstNodeListIterator<L, N> {}
466
467impl<L: Language, N: AstNode<Language = L>> FusedIterator for AstNodeListIterator<L, N> {}
468
469impl<L: Language, N: AstNode<Language = L>> DoubleEndedIterator for AstNodeListIterator<L, N> {
470    fn next_back(&mut self) -> Option<Self::Item> {
471        Some(Self::slot_to_node(&self.inner.next_back()?))
472    }
473}
474
475#[derive(Clone, Eq, PartialEq)]
476#[cfg_attr(feature = "serde", derive(Serialize))]
477pub struct AstSeparatedElement<L: Language, N> {
478    pub node: SyntaxResult<N>,
479    pub trailing_separator: SyntaxResult<Option<SyntaxToken<L>>>,
480}
481
482impl<L: Language, N: AstNode<Language = L>> AstSeparatedElement<L, N> {
483    pub fn node(&self) -> SyntaxResult<&N> {
484        match &self.node {
485            Ok(node) => Ok(node),
486            Err(err) => Err(*err),
487        }
488    }
489
490    pub fn into_node(self) -> SyntaxResult<N> {
491        self.node
492    }
493
494    pub fn trailing_separator(&self) -> SyntaxResult<Option<&SyntaxToken<L>>> {
495        match &self.trailing_separator {
496            Ok(Some(sep)) => Ok(Some(sep)),
497            Ok(_) => Ok(None),
498            Err(err) => Err(*err),
499        }
500    }
501
502    pub fn into_trailing_separator(self) -> SyntaxResult<Option<SyntaxToken<L>>> {
503        self.trailing_separator
504    }
505}
506
507impl<L: Language, N: Debug> Debug for AstSeparatedElement<L, N> {
508    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
509        match &self.node {
510            Ok(node) => N::fmt(node, f)?,
511            Err(_) => f.write_str("missing element")?,
512        };
513        match &self.trailing_separator {
514            Ok(Some(separator)) => {
515                f.write_str(",\n")?;
516                Debug::fmt(&separator, f)
517            }
518            Err(_) => f.write_str(",\nmissing separator"),
519            Ok(None) => Ok(()),
520        }
521    }
522}
523
524/// List of nodes where every two nodes are separated by a token.
525/// For example, the elements of an array where every two elements are separated by a comma token.
526/// The list expects that the underlying syntax node has a slot for every node and separator
527/// even if they are missing from the source code. For example, a list for `a b` where the `,` separator
528/// is missing contains the slots `Node(a), Empty, Node(b)`. This also applies for missing nodes:
529/// the list for `, b,` must have the slots `Empty, Token(,), Node(b), Token(,)`.
530pub trait AstSeparatedList {
531    type Language: Language;
532    type Node: AstNode<Language = Self::Language>;
533
534    /// Returns the underlying syntax list
535    fn syntax_list(&self) -> &SyntaxList<Self::Language>;
536
537    /// Returns the underlying syntax list
538    fn into_syntax_list(self) -> SyntaxList<Self::Language>;
539
540    /// Returns an iterator over all nodes with their trailing separator
541    fn elements(&self) -> AstSeparatedListElementsIterator<Self::Language, Self::Node> {
542        AstSeparatedListElementsIterator::new(self.syntax_list())
543    }
544
545    /// Returns an iterator over all separator tokens
546    fn separators(&self) -> AstSeparatorIterator<Self::Language, Self::Node> {
547        AstSeparatorIterator {
548            inner: self.elements(),
549        }
550    }
551
552    /// Returns an iterator over all nodes
553    fn iter(&self) -> AstSeparatedListNodesIterator<Self::Language, Self::Node> {
554        AstSeparatedListNodesIterator {
555            inner: self.elements(),
556        }
557    }
558
559    /// Returns the first node
560    fn first(&self) -> Option<SyntaxResult<Self::Node>> {
561        self.iter().next()
562    }
563
564    /// Returns the last node
565    fn last(&self) -> Option<SyntaxResult<Self::Node>> {
566        self.iter().next_back()
567    }
568
569    #[inline]
570    fn is_empty(&self) -> bool {
571        self.len() == 0
572    }
573
574    fn len(&self) -> usize {
575        (self.syntax_list().len() + 1) / 2
576    }
577
578    fn trailing_separator(&self) -> Option<SyntaxToken<Self::Language>> {
579        match self.syntax_list().last()? {
580            SyntaxSlot::Token(token) => Some(token),
581            _ => None,
582        }
583    }
584}
585
586pub struct AstSeparatorIterator<L: Language, N> {
587    inner: AstSeparatedListElementsIterator<L, N>,
588}
589
590impl<L, N> Iterator for AstSeparatorIterator<L, N>
591where
592    L: Language,
593    N: AstNode<Language = L>,
594{
595    type Item = SyntaxResult<SyntaxToken<L>>;
596
597    fn next(&mut self) -> Option<Self::Item> {
598        loop {
599            let element = self.inner.next()?;
600
601            match element.trailing_separator {
602                Ok(Some(separator)) => return Some(Ok(separator)),
603                Err(missing) => return Some(Err(missing)),
604                _ => {}
605            }
606        }
607    }
608}
609
610impl<L, N> DoubleEndedIterator for AstSeparatorIterator<L, N>
611where
612    L: Language,
613    N: AstNode<Language = L>,
614{
615    fn next_back(&mut self) -> Option<Self::Item> {
616        loop {
617            let element = self.inner.next_back()?;
618
619            match element.trailing_separator {
620                Ok(Some(separator)) => return Some(Ok(separator)),
621                Err(missing) => return Some(Err(missing)),
622                _ => {}
623            }
624        }
625    }
626}
627
628#[derive(Debug, Clone)]
629pub struct AstSeparatedListElementsIterator<L: Language, N> {
630    slots: SyntaxSlots<L>,
631    ph: PhantomData<N>,
632}
633
634impl<L: Language, N: AstNode<Language = L>> AstSeparatedListElementsIterator<L, N> {
635    fn new(list: &SyntaxList<L>) -> Self {
636        Self {
637            slots: list.iter(),
638            ph: PhantomData,
639        }
640    }
641}
642
643impl<L: Language, N: AstNode<Language = L>> Iterator for AstSeparatedListElementsIterator<L, N> {
644    type Item = AstSeparatedElement<L, N>;
645
646    fn next(&mut self) -> Option<Self::Item> {
647        let slot = self.slots.next()?;
648
649        let node = match slot {
650            // The node for this element is missing if the next child is a token instead of a node.
651            SyntaxSlot::Token(token) => panic!("Malformed list, node expected but found token {token:?} instead. You must add missing markers for missing elements."),
652            // Missing element
653            SyntaxSlot::Empty { .. } => Err(SyntaxError::MissingRequiredChild),
654            SyntaxSlot::Node(node) => Ok(N::unwrap_cast(node))
655        };
656
657        let separator = match self.slots.next() {
658            Some(SyntaxSlot::Empty { .. }) => Err(
659                SyntaxError::MissingRequiredChild,
660            ),
661            Some(SyntaxSlot::Token(token)) => Ok(Some(token)),
662            // End of list, no trailing separator
663            None => Ok(None),
664            Some(SyntaxSlot::Node(node)) => panic!("Malformed separated list, separator expected but found node {node:?} instead. You must add missing markers for missing separators."),
665        };
666
667        Some(AstSeparatedElement {
668            node,
669            trailing_separator: separator,
670        })
671    }
672}
673
674impl<L: Language, N: AstNode<Language = L>> FusedIterator
675    for AstSeparatedListElementsIterator<L, N>
676{
677}
678
679impl<L: Language, N: AstNode<Language = L>> DoubleEndedIterator
680    for AstSeparatedListElementsIterator<L, N>
681{
682    fn next_back(&mut self) -> Option<Self::Item> {
683        let first_slot = self.slots.next_back()?;
684
685        let separator = match first_slot {
686            SyntaxSlot::Node(node) => {
687                // if we fallback here, it means that we are at the end of the iterator
688                // which means that we don't have the optional separator and
689                // we have only a node, we bail early.
690                return Some(AstSeparatedElement {
691                    node: Ok(N::unwrap_cast(node)),
692                    trailing_separator: Ok(None),
693                });
694            }
695            SyntaxSlot::Token(token) => Ok(Some(token)),
696            SyntaxSlot::Empty { .. } => Ok(None),
697        };
698
699        let node = match self.slots.next_back() {
700            None => panic!("Malformed separated list, expected a node but found none"),
701            Some(SyntaxSlot::Empty{ .. }) => Err(SyntaxError::MissingRequiredChild),
702            Some(SyntaxSlot::Token(token)) => panic!("Malformed list, node expected but found token {token:?} instead. You must add missing markers for missing elements."),
703            Some(SyntaxSlot::Node(node)) => {
704                Ok(N::unwrap_cast(node))
705            }
706        };
707
708        Some(AstSeparatedElement {
709            node,
710            trailing_separator: separator,
711        })
712    }
713}
714
715#[derive(Debug, Clone)]
716pub struct AstSeparatedListNodesIterator<L: Language, N> {
717    inner: AstSeparatedListElementsIterator<L, N>,
718}
719
720impl<L: Language, N: AstNode<Language = L>> Iterator for AstSeparatedListNodesIterator<L, N> {
721    type Item = SyntaxResult<N>;
722    fn next(&mut self) -> Option<Self::Item> {
723        self.inner.next().map(|element| element.node)
724    }
725}
726
727impl<L: Language, N: AstNode<Language = L>> FusedIterator for AstSeparatedListNodesIterator<L, N> {}
728
729impl<L: Language, N: AstNode<Language = L>> DoubleEndedIterator
730    for AstSeparatedListNodesIterator<L, N>
731{
732    fn next_back(&mut self) -> Option<Self::Item> {
733        self.inner.next_back().map(|element| element.node)
734    }
735}
736
737/// Specific result used when navigating nodes using AST APIs
738pub type SyntaxResult<ResultType> = Result<ResultType, SyntaxError>;
739
740#[derive(Debug, Eq, PartialEq, Clone, Copy)]
741#[cfg_attr(feature = "serde", derive(Serialize))]
742pub enum SyntaxError {
743    /// Error thrown when a mandatory node is not found
744    MissingRequiredChild,
745
746    /// Error thrown when a metavariable node is found in an unexpected context
747    UnexpectedMetavariable,
748}
749
750impl Display for SyntaxError {
751    fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
752        match self {
753            SyntaxError::MissingRequiredChild => fmt.write_str("missing required child"),
754            SyntaxError::UnexpectedMetavariable => fmt.write_str("unexpectedd metavariable node"),
755        }
756    }
757}
758
759impl Error for SyntaxError {}
760
761pub mod support {
762    use super::{AstNode, SyntaxNode, SyntaxToken};
763
764    use super::{Language, SyntaxError, SyntaxResult};
765    use crate::syntax::SyntaxSlot;
766    use crate::SyntaxElementChildren;
767    use std::fmt::{Debug, Formatter};
768
769    pub fn node<L: Language, N: AstNode<Language = L>>(
770        parent: &SyntaxNode<L>,
771        slot_index: usize,
772    ) -> Option<N> {
773        match parent.slots().nth(slot_index)? {
774            SyntaxSlot::Empty { .. } => None,
775            SyntaxSlot::Node(node) => Some(N::unwrap_cast(node)),
776            SyntaxSlot::Token(token) => {
777                panic!("expected a node in the slot {slot_index} but found token {token:?}")
778            }
779        }
780    }
781
782    pub fn required_node<L: Language, N: AstNode<Language = L>>(
783        parent: &SyntaxNode<L>,
784        slot_index: usize,
785    ) -> SyntaxResult<N> {
786        self::node(parent, slot_index).ok_or(SyntaxError::MissingRequiredChild)
787    }
788
789    pub fn elements<L: Language>(parent: &SyntaxNode<L>) -> SyntaxElementChildren<L> {
790        parent.children_with_tokens()
791    }
792
793    pub fn list<L: Language, N: AstNode<Language = L>>(
794        parent: &SyntaxNode<L>,
795        slot_index: usize,
796    ) -> N {
797        required_node(parent, slot_index)
798            .unwrap_or_else(|_| panic!("expected a list in slot {slot_index} of {parent:?}"))
799    }
800
801    pub fn token<L: Language>(parent: &SyntaxNode<L>, slot_index: usize) -> Option<SyntaxToken<L>> {
802        match parent.slots().nth(slot_index)? {
803            SyntaxSlot::Empty { .. } => None,
804            SyntaxSlot::Token(token) => Some(token),
805            SyntaxSlot::Node(node) => {
806                panic!("expected a token in the slot {slot_index} but found node {node:?}")
807            }
808        }
809    }
810
811    pub fn required_token<L: Language>(
812        parent: &SyntaxNode<L>,
813        slot_index: usize,
814    ) -> SyntaxResult<SyntaxToken<L>> {
815        token(parent, slot_index).ok_or(SyntaxError::MissingRequiredChild)
816    }
817
818    /// New-type wrapper to flatten the debug output of syntax result fields when printing [AstNode]s.
819    /// Omits the [Ok] if the node is present and prints `missing (required)` if the child is missing
820    pub struct DebugSyntaxResult<N>(pub SyntaxResult<N>);
821
822    impl<N: Debug> Debug for DebugSyntaxResult<N> {
823        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
824            match &self.0 {
825                Ok(node) => std::fmt::Debug::fmt(node, f),
826                Err(SyntaxError::MissingRequiredChild) => f.write_str("missing (required)"),
827                Err(SyntaxError::UnexpectedMetavariable) => f.write_str("metavariable"),
828            }
829        }
830    }
831
832    /// New-type wrapper to flatten the debug output of optional children when printing [AstNode]s.
833    /// Omits the [Some] if the node is present and prints `missing (optional)` if the child is missing
834    pub struct DebugOptionalElement<N>(pub Option<N>);
835
836    impl<N: Debug> Debug for DebugOptionalElement<N> {
837        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
838            match &self.0 {
839                Some(node) => std::fmt::Debug::fmt(node, f),
840                None => f.write_str("missing (optional)"),
841            }
842        }
843    }
844}
845
846#[cfg(test)]
847mod tests {
848    use crate::raw_language::{
849        LiteralExpression, RawLanguage, RawLanguageKind, RawSyntaxTreeBuilder,
850        SeparatedExpressionList,
851    };
852    use crate::{AstNode, AstSeparatedElement, AstSeparatedList, SyntaxResult};
853
854    /// Creates a ast separated list over a sequence of numbers separated by ",".
855    /// The elements are pairs of: (value, separator).
856    fn build_list<'a>(
857        elements: impl IntoIterator<Item = (Option<i32>, Option<&'a str>)>,
858    ) -> SeparatedExpressionList {
859        let mut builder = RawSyntaxTreeBuilder::new();
860
861        builder.start_node(RawLanguageKind::SEPARATED_EXPRESSION_LIST);
862
863        for (node, separator) in elements {
864            if let Some(node) = node {
865                builder.start_node(RawLanguageKind::LITERAL_EXPRESSION);
866                builder.token(RawLanguageKind::NUMBER_TOKEN, node.to_string().as_str());
867                builder.finish_node();
868            }
869
870            if let Some(separator) = separator {
871                builder.token(RawLanguageKind::COMMA_TOKEN, separator);
872            }
873        }
874
875        builder.finish_node();
876
877        let node = builder.finish();
878
879        SeparatedExpressionList::new(node.into_list())
880    }
881
882    type MappedElement = Vec<(Option<f64>, Option<String>)>;
883
884    fn map_elements<'a>(
885        actual: impl DoubleEndedIterator<Item = AstSeparatedElement<RawLanguage, LiteralExpression>>,
886        expected: impl IntoIterator<Item = (Option<f64>, Option<&'a str>)>,
887        revert: bool,
888    ) -> (MappedElement, MappedElement) {
889        let actual: Vec<_> = if revert {
890            actual.rev().collect()
891        } else {
892            actual.collect()
893        };
894        let actual = actual
895            .into_iter()
896            .map(|element| {
897                (
898                    element.node.ok().map(|n| n.text().parse::<f64>().unwrap()),
899                    element
900                        .trailing_separator
901                        .ok()
902                        .flatten()
903                        .map(|separator| separator.text().to_string()),
904                )
905            })
906            .collect::<Vec<_>>();
907
908        let expected = expected
909            .into_iter()
910            .map(|(value, separator)| (value, separator.map(|sep| sep.to_string())))
911            .collect::<Vec<_>>();
912
913        (actual, expected)
914    }
915
916    fn assert_elements<'a>(
917        actual: impl DoubleEndedIterator<Item = AstSeparatedElement<RawLanguage, LiteralExpression>>,
918        expected: impl IntoIterator<Item = (Option<f64>, Option<&'a str>)>,
919    ) {
920        let (actual, expected) = map_elements(actual, expected, false);
921
922        assert_eq!(actual, expected);
923    }
924
925    fn assert_rev_elements<'a>(
926        actual: impl DoubleEndedIterator<Item = AstSeparatedElement<RawLanguage, LiteralExpression>>,
927        expected: impl IntoIterator<Item = (Option<f64>, Option<&'a str>)>,
928    ) {
929        let (actual, expected) = map_elements(actual, expected, true);
930
931        assert_eq!(actual, expected);
932    }
933
934    fn assert_nodes(
935        actual: impl Iterator<Item = SyntaxResult<LiteralExpression>>,
936        expected: impl IntoIterator<Item = f64>,
937    ) {
938        assert_eq!(
939            actual
940                .map(|literal| literal.unwrap().text().parse::<f64>().unwrap())
941                .collect::<Vec<_>>(),
942            expected.into_iter().collect::<Vec<_>>()
943        );
944    }
945
946    #[test]
947    fn empty() {
948        let list = build_list(vec![]);
949
950        assert_eq!(list.len(), 0);
951        assert!(list.is_empty());
952        assert_eq!(list.separators().count(), 0);
953
954        assert_nodes(list.iter(), vec![]);
955        assert_elements(list.elements(), vec![]);
956        assert_rev_elements(list.elements(), vec![]);
957        assert_eq!(list.trailing_separator(), None);
958    }
959
960    #[test]
961    fn separated_list() {
962        let list = build_list(vec![
963            (Some(1), Some(",")),
964            (Some(2), Some(",")),
965            (Some(3), Some(",")),
966            (Some(4), None),
967        ]);
968
969        assert_eq!(list.len(), 4);
970        assert!(!list.is_empty());
971        assert_eq!(list.separators().count(), 3);
972
973        assert_nodes(list.iter(), vec![1., 2., 3., 4.]);
974        assert_elements(
975            list.elements(),
976            vec![
977                (Some(1.), Some(",")),
978                (Some(2.), Some(",")),
979                (Some(3.), Some(",")),
980                (Some(4.), None),
981            ],
982        );
983        assert_rev_elements(
984            list.elements(),
985            vec![
986                (Some(4.), None),
987                (Some(3.), Some(",")),
988                (Some(2.), Some(",")),
989                (Some(1.), Some(",")),
990            ],
991        );
992        assert_eq!(list.trailing_separator(), None);
993    }
994
995    #[test]
996    fn double_iterator_meet_at_middle() {
997        let list = build_list(vec![
998            (Some(1), Some(",")),
999            (Some(2), Some(",")),
1000            (Some(3), Some(",")),
1001            (Some(4), None),
1002        ]);
1003
1004        let mut iter = list.elements();
1005
1006        let element = iter.next().unwrap();
1007        assert_eq!(element.node().unwrap().text(), "1");
1008        let element = iter.next_back().unwrap();
1009        assert_eq!(element.node().unwrap().text(), "4");
1010
1011        let element = iter.next().unwrap();
1012        assert_eq!(element.node().unwrap().text(), "2");
1013        let element = iter.next_back().unwrap();
1014        assert_eq!(element.node().unwrap().text(), "3");
1015
1016        assert!(iter.next().is_none());
1017        assert!(iter.next_back().is_none());
1018    }
1019
1020    #[test]
1021    fn separated_with_trailing() {
1022        // list(1, 2, 3, 4,)
1023        let list = build_list(vec![
1024            (Some(1), Some(",")),
1025            (Some(2), Some(",")),
1026            (Some(3), Some(",")),
1027            (Some(4), Some(",")),
1028        ]);
1029
1030        assert_eq!(list.len(), 4);
1031        assert!(!list.is_empty());
1032        assert_nodes(list.iter(), vec![1., 2., 3., 4.]);
1033        assert_eq!(list.separators().count(), 4);
1034
1035        assert_elements(
1036            list.elements(),
1037            vec![
1038                (Some(1.), Some(",")),
1039                (Some(2.), Some(",")),
1040                (Some(3.), Some(",")),
1041                (Some(4.), Some(",")),
1042            ],
1043        );
1044        assert_rev_elements(
1045            list.elements(),
1046            vec![
1047                (Some(4.), Some(",")),
1048                (Some(3.), Some(",")),
1049                (Some(2.), Some(",")),
1050                (Some(1.), Some(",")),
1051            ],
1052        );
1053        assert!(list.trailing_separator().is_some());
1054    }
1055
1056    #[test]
1057    fn separated_with_two_successive_separators() {
1058        // list([1,,])
1059        let list = build_list(vec![(Some(1), Some(",")), (None, Some(","))]);
1060
1061        assert_eq!(list.len(), 2);
1062        assert!(!list.is_empty());
1063        assert_eq!(list.separators().count(), 2);
1064
1065        assert_elements(
1066            list.elements(),
1067            vec![(Some(1.), Some(",")), (None, Some(","))],
1068        );
1069
1070        assert_rev_elements(
1071            list.elements(),
1072            vec![(None, Some(",")), (Some(1.), Some(","))],
1073        );
1074    }
1075
1076    #[test]
1077    fn separated_with_leading_separator() {
1078        // list([,3])
1079        let list = build_list(vec![(None, Some(",")), (Some(3), None)]);
1080
1081        assert_eq!(list.len(), 2);
1082        assert!(!list.is_empty());
1083        assert_eq!(list.separators().count(), 1);
1084
1085        assert_elements(
1086            list.elements(),
1087            vec![
1088                // missing first element
1089                (None, Some(",")),
1090                (Some(3.), None),
1091            ],
1092        );
1093
1094        assert_rev_elements(
1095            list.elements(),
1096            vec![
1097                // missing first element
1098                (Some(3.), None),
1099                (None, Some(",")),
1100            ],
1101        );
1102    }
1103
1104    #[test]
1105    fn separated_with_two_successive_nodes() {
1106        // list([1 2,])
1107        let list = build_list(vec![(Some(1), None), (Some(2), Some(","))]);
1108
1109        assert_eq!(list.len(), 2);
1110        assert!(!list.is_empty());
1111        assert_eq!(list.separators().count(), 2);
1112
1113        assert_elements(
1114            list.elements(),
1115            vec![(Some(1.), None), (Some(2.), Some(","))],
1116        );
1117
1118        assert_rev_elements(
1119            list.elements(),
1120            vec![(Some(2.), Some(",")), (Some(1.), None)],
1121        );
1122    }
1123
1124    #[test]
1125    fn ok_typed_parent_navigation() {
1126        use crate::ast::SyntaxNodeCast;
1127        use crate::raw_language::{RawLanguage, RawLanguageKind, RawSyntaxTreeBuilder};
1128        use crate::*;
1129
1130        // This test creates the following tree
1131        // Root
1132        //     Condition
1133        //         Let
1134        // then selects the CONDITION node, cast it,
1135        // then navigate upwards to its parent.
1136        // All casts are fake and implemented below
1137
1138        let tree = RawSyntaxTreeBuilder::wrap_with_node(RawLanguageKind::ROOT, |builder| {
1139            builder.start_node(RawLanguageKind::CONDITION);
1140            builder.token(RawLanguageKind::LET_TOKEN, "let");
1141            builder.finish_node();
1142        });
1143        let typed = tree.first_child().unwrap().cast::<RawRoot>().unwrap();
1144        let _ = typed.parent::<RawRoot>().unwrap();
1145
1146        #[derive(Clone)]
1147        struct RawRoot(SyntaxNode<RawLanguage>);
1148        impl AstNode for RawRoot {
1149            type Language = RawLanguage;
1150
1151            const KIND_SET: SyntaxKindSet<Self::Language> =
1152                SyntaxKindSet::from_raw(RawSyntaxKind(RawLanguageKind::ROOT as u16));
1153
1154            fn can_cast(_: <Self::Language as Language>::Kind) -> bool {
1155                todo!()
1156            }
1157
1158            fn cast(syntax: SyntaxNode<Self::Language>) -> Option<Self>
1159            where
1160                Self: Sized,
1161            {
1162                Some(Self(syntax))
1163            }
1164
1165            fn syntax(&self) -> &SyntaxNode<Self::Language> {
1166                &self.0
1167            }
1168
1169            fn into_syntax(self) -> SyntaxNode<Self::Language> {
1170                todo!()
1171            }
1172        }
1173    }
1174}
biome_rowan/ast/mod.rs

biome_rowan/ast/
mod.rs
