rune/grammar/
tree.rs

Help
1use core::fmt;
2use core::mem::{replace, take};
3
4use rust_alloc::rc::Rc;
5
6use crate::alloc;
7use crate::alloc::prelude::*;
8use crate::ast::{Kind, Span, Spanned, ToAst, Token};
9use crate::compile::{Error, ErrorKind, Result, WithSpan};
10#[cfg(feature = "fmt")]
11use crate::fmt::Formatter;
12use crate::grammar::ws;
13use crate::parse::{Expectation, IntoExpectation};
14use crate::shared::FixedVec;
15use crate::SourceId;
16#[cfg(feature = "std")]
17use crate::Sources;
18
19use super::Flavor;
20
21pub(super) type InternalNode<'a> = syntree::Node<'a, Kind, Flavor>;
22pub(super) type InternalChildren<'a> = syntree::node::Children<'a, Kind, Flavor>;
23
24pub(crate) trait Ignore<'a> {
25    /// Capture an error.
26    fn error(&mut self, error: Error) -> alloc::Result<()>;
27
28    /// Ignore the given node.
29    fn ignore(&mut self, node: Node<'a>) -> Result<()>;
30}
31
32#[derive(Debug, Default)]
33pub(crate) struct Tree {
34    inner: syntree::Tree<Kind, Flavor>,
35}
36
37impl Tree {
38    pub(super) fn new(inner: syntree::Tree<Kind, Flavor>) -> Self {
39        Self { inner }
40    }
41
42    /// Construt a root for the tree.
43    pub(crate) fn node_at(self: &Rc<Self>, source_id: SourceId, NodeId(id): NodeId) -> NodeAt {
44        NodeAt {
45            tree: self.clone(),
46            source_id,
47            id,
48        }
49    }
50
51    /// Get a reference to a node.
52    pub(crate) fn get(&self, id: syntree::pointer::PointerUsize) -> Option<Node<'_>> {
53        self.inner.get(id).map(Node::new)
54    }
55
56    /// Get the children as an array ignoring whitespace.
57    pub(crate) fn nodes<const N: usize>(&self) -> Option<[Node<'_>; N]> {
58        self.fixed_vec(Node::new)?.try_into_inner()
59    }
60
61    /// Get the children as a fixed array ignoring whitespace.
62    fn fixed_vec<'a, const N: usize, T>(
63        &'a self,
64        factory: fn(InternalNode<'a>) -> T,
65    ) -> Option<FixedVec<T, N>> {
66        let mut vec = FixedVec::new();
67
68        for node in self
69            .inner
70            .children()
71            .filter(|n| !matches!(n.value(), ws!()))
72        {
73            if vec.try_push(factory(node)).is_err() {
74                return None;
75            }
76        }
77
78        Some(vec)
79    }
80
81    /// Iterate over all the children of the tree.
82    pub(crate) fn parse_all<'a, P>(&'a self, mut parser: P) -> Result<()>
83    where
84        P: FnMut(&mut Stream<'a>) -> Result<()>,
85    {
86        for node in self
87            .inner
88            .children()
89            .filter(|n| !matches!(n.value(), ws!()))
90        {
91            let mut p = Stream::new(node);
92            parser(&mut p)?;
93            p.end()?;
94        }
95
96        Ok(())
97    }
98
99    /// Walk the tree.
100    #[cfg(feature = "fmt")]
101    pub(crate) fn walk(&self) -> impl Iterator<Item = Node<'_>> {
102        self.inner.walk().map(Node::new)
103    }
104
105    /// Print the tree to the given writer.
106    #[cfg(feature = "std")]
107    pub(crate) fn print_with_source(
108        &self,
109        span: &dyn Spanned,
110        title: impl fmt::Display,
111        source: &str,
112    ) -> Result<()> {
113        use std::io::Write;
114
115        let o = std::io::stdout();
116        let mut o = o.lock();
117
118        writeln!(o, "{title}:").with_span(span)?;
119
120        for (depth, node) in self.inner.walk().with_depths() {
121            let n = (depth * 2) as usize;
122            let data = node.value();
123            let span = node.span();
124
125            if node.has_children() {
126                writeln!(o, "{:n$}{:?}@{}", "", data, span).with_span(span)?;
127            } else if let Some(source) = source.get(span.range()) {
128                writeln!(o, "{:n$}{:?}@{} {:?}", "", data, span, source).with_span(span)?;
129            } else {
130                writeln!(o, "{:n$}{:?}@{} +", "", data, span).with_span(span)?;
131            }
132        }
133
134        Ok(())
135    }
136
137    /// Print the tree to the given writer.
138    #[cfg(feature = "std")]
139    pub(crate) fn print(&self, span: &dyn Spanned, title: impl fmt::Display) -> Result<()> {
140        use std::io::Write;
141
142        let o = std::io::stdout();
143        let mut o = o.lock();
144
145        writeln!(o, "{title}:").with_span(span)?;
146
147        for (depth, node) in self.inner.walk().with_depths() {
148            let n = (depth * 2) as usize;
149            let data = node.value();
150            let span = node.span();
151
152            if node.has_children() {
153                writeln!(o, "{:n$}{:?}@{}", "", data, span).with_span(span)?;
154            } else {
155                writeln!(o, "{:n$}{:?}@{} +", "", data, span).with_span(span)?;
156            }
157        }
158
159        Ok(())
160    }
161}
162
163/// Iterator over the children of a tree.
164pub(crate) struct StreamBuf<'a> {
165    stream: Stream<'a>,
166}
167
168impl<'a> StreamBuf<'a> {
169    /// Test if the stream is end-of-file.
170    pub(crate) fn is_eof(&mut self) -> bool {
171        self.stream.is_eof()
172    }
173
174    /// Parse the stream being referenced.
175    pub(crate) fn parse<P, O>(mut self, parser: P) -> Result<O>
176    where
177        P: FnOnce(&mut Stream<'a>) -> Result<O>,
178    {
179        let out = parser(&mut self.stream)?;
180        self.stream.end()?;
181        Ok(out)
182    }
183}
184
185impl Spanned for StreamBuf<'_> {
186    #[inline]
187    fn span(&self) -> Span {
188        self.stream.span()
189    }
190}
191
192impl<'a> Iterator for StreamBuf<'a> {
193    type Item = Node<'a>;
194
195    #[inline]
196    fn next(&mut self) -> Option<Self::Item> {
197        self.stream.next()
198    }
199}
200
201impl fmt::Debug for StreamBuf<'_> {
202    #[inline]
203    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
204        self.stream.fmt(f)
205    }
206}
207
208/// Iterator over the children of a tree.
209pub(crate) struct Stream<'a> {
210    node: InternalNode<'a>,
211    iter: Iter<'a>,
212    peek: Option<InternalNode<'a>>,
213}
214
215impl<'a> Stream<'a> {
216    pub(crate) fn new(node: InternalNode<'a>) -> Self {
217        Self {
218            node,
219            iter: Iter::new(node.first(), node.last()),
220            peek: None,
221        }
222    }
223
224    /// Ignore the remainder of the stream.
225    pub(crate) fn ignore(&mut self) {
226        self.iter = Iter::default();
227        self.peek = None;
228    }
229
230    /// Coerce into remaining inner parser.
231    pub(crate) fn take_remaining(&mut self) -> StreamBuf<'a> {
232        StreamBuf {
233            stream: Stream {
234                node: self.node,
235                iter: take(&mut self.iter),
236                peek: self.peek.take(),
237            },
238        }
239    }
240
241    /// Get a clone of the raw current state of children.
242    #[cfg(feature = "fmt")]
243    pub(crate) fn children(&self) -> impl Iterator<Item = Node<'a>> + '_ {
244        self.iter.clone().map(Node::new)
245    }
246
247    /// Get a clone of the raw current state of children.
248    #[cfg(feature = "fmt")]
249    pub(crate) fn write_remaining(&mut self, o: &mut Formatter<'a>) -> Result<()> {
250        o.flush_whitespace(false)?;
251
252        for node in self.peek.take().into_iter().chain(self.iter.by_ref()) {
253            o.write_raw(Node::new(node))?;
254        }
255
256        Ok(())
257    }
258
259    /// Get a clone of the raw current state of children.
260    #[cfg(feature = "fmt")]
261    pub(crate) fn fmt_remaining_trimmed(&mut self, o: &mut Formatter<'a>) -> Result<()> {
262        o.flush_whitespace(false)?;
263
264        let mut buf = None;
265        let mut first = true;
266        let mut last_was_line = false;
267
268        let iter = self.peek.take().into_iter().chain(self.iter.by_ref());
269
270        for node in iter {
271            if node.has_children() {
272                continue;
273            }
274
275            if matches!(node.value(), Kind::Whitespace) {
276                buf = Some(Node::new(node));
277                continue;
278            }
279
280            if !first {
281                if let Some(buf) = buf.take() {
282                    o.write_raw(buf)?;
283                }
284            }
285
286            last_was_line = matches!(node.value(), Kind::Comment);
287            o.write_raw(Node::new(node))?;
288            first = false;
289        }
290
291        // Since we've trimmed the last whitespace, we need to add the
292        // corresponding number of lines here.
293        if last_was_line {
294            o.nl(1)?;
295        }
296
297        Ok(())
298    }
299
300    /// Get the kind of the current node.
301    pub(crate) fn kind(&self) -> Kind {
302        self.node.value()
303    }
304
305    /// Get kinds of all children excluding whitespace.
306    pub(crate) fn kinds<const N: usize>(&self) -> Option<[Kind; N]> {
307        self.node().kinds()
308    }
309
310    /// Get all children excluding whitespace.
311    pub(crate) fn nodes<const N: usize>(&self) -> Option<[Node<'a>; N]> {
312        self.node().nodes()
313    }
314
315    /// Test if the parser is at the end of input.
316    pub(crate) fn is_eof(&mut self) -> bool {
317        matches!(self.peek(), Kind::Eof)
318    }
319
320    /// Get the identifier of the node.
321    pub(crate) fn id(&self) -> NodeId {
322        NodeId(self.node.id())
323    }
324
325    /// Get the current parser as a node.
326    #[inline]
327    pub(crate) fn node(&self) -> Node<'a> {
328        Node::new(self.node)
329    }
330
331    /// Peek the next node.
332    pub(crate) fn peek(&mut self) -> Kind {
333        if let Some(value) = self.peek_node() {
334            return value.value();
335        }
336
337        Kind::Eof
338    }
339
340    /// Get the current span of the parser.
341    pub(crate) fn peek_span(&mut self) -> Span {
342        if let Some(node) = self.peek_node() {
343            return inner_span(node.span());
344        }
345
346        Span::point(self.node.span().end)
347    }
348
349    fn peek_node(&mut self) -> Option<&syntree::Node<Kind, Flavor>> {
350        if self.peek.is_none() {
351            if let Some(node) = self.next_node() {
352                self.peek = Some(node);
353            }
354        }
355
356        self.peek.as_ref()
357    }
358
359    /// Report an unsupported error for the next item being peeked.
360    pub(crate) fn expected_peek(&mut self, expected: impl IntoExpectation) -> Error {
361        Error::new(
362            self.peek_span(),
363            ErrorKind::ExpectedSyntax {
364                expected: expected.into_expectation(),
365                actual: self.kind().into_expectation(),
366            },
367        )
368    }
369
370    /// Report an unsupported error for the current tree parser.
371    pub(crate) fn expected(&mut self, expected: impl IntoExpectation) -> Error {
372        Error::new(
373            self.span(),
374            ErrorKind::ExpectedSyntax {
375                expected: expected.into_expectation(),
376                actual: self.kind().into_expectation(),
377            },
378        )
379    }
380
381    /// Expect and discard all the given kinds.
382    pub(crate) fn all<const N: usize>(&mut self, expected: [Kind; N]) -> Result<()> {
383        for kind in expected {
384            self.expect(kind)?;
385        }
386
387        Ok(())
388    }
389
390    /// Require that there is at least one more child node.
391    pub(crate) fn expect(&mut self, expected: Kind) -> Result<Node<'a>> {
392        let Some(node) = self.next_node() else {
393            return Err(Error::new(
394                self.peek_span(),
395                ErrorKind::UnexpectedEndOfSyntaxWith {
396                    inside: self.kind().into_expectation(),
397                    expected: expected.into_expectation(),
398                },
399            ));
400        };
401
402        if node.value() != expected {
403            return Err(Error::new(
404                inner_span(node.span()),
405                ErrorKind::ExpectedSyntaxIn {
406                    inside: self.kind().into_expectation(),
407                    expected: expected.into_expectation(),
408                    actual: node.value().into_expectation(),
409                },
410            ));
411        }
412
413        Ok(Node::new(node))
414    }
415
416    /// Require that there is at least one more child node.
417    pub(crate) fn pump(&mut self) -> Result<Node<'a>> {
418        let Some(node) = self.next_node() else {
419            return Err(Error::new(
420                self.peek_span(),
421                ErrorKind::UnexpectedEndOfSyntax {
422                    inside: self.kind().into_expectation(),
423                },
424            ));
425        };
426
427        Ok(Node::new(node))
428    }
429
430    /// Helper to coerce the next node into an ast element.
431    pub(crate) fn ast<T>(&mut self) -> Result<T>
432    where
433        T: ToAst,
434    {
435        let Some(node) = self.next_node() else {
436            return Err(Error::new(
437                self.peek_span(),
438                ErrorKind::UnexpectedEndOfSyntaxWith {
439                    inside: self.kind().into_expectation(),
440                    expected: T::into_expectation(),
441                },
442            ));
443        };
444
445        Node::new(node).ast()
446    }
447
448    /// Try to eat and return one node.
449    pub(crate) fn eat(&mut self, expect: Kind) -> MaybeNode<'a> {
450        self.eat_matching(|kind| kind == expect)
451    }
452
453    /// Try to eat and return one node.
454    pub(crate) fn try_ast<T>(&mut self) -> Result<Option<T>>
455    where
456        T: ToAst,
457    {
458        match self.eat_matching(|kind| T::matches(&kind)) {
459            MaybeNode::Some(node) => Ok(Some(node.ast()?)),
460            MaybeNode::None => Ok(None),
461        }
462    }
463
464    /// Try to eat and return one node.
465    pub(crate) fn eat_matching<F>(&mut self, mut filter: F) -> MaybeNode<'a>
466    where
467        F: FnMut(Kind) -> bool,
468    {
469        if let Some(node) = self.next_node() {
470            if filter(node.value()) {
471                return MaybeNode::Some(Node::new(node));
472            }
473
474            self.peek = Some(node);
475        }
476
477        MaybeNode::None
478    }
479
480    /// Read remaining nodes equal to the given kind.
481    pub(crate) fn remaining(
482        &mut self,
483        o: &mut dyn Ignore<'a>,
484        expected: Kind,
485    ) -> Result<Remaining<'a>> {
486        let mut first = None;
487        let mut trailing = None::<Span>;
488        let mut out = MaybeNode::None;
489        let mut count = 0;
490
491        while let Some(node) = self.next_node() {
492            if node.value() != expected {
493                if let Some(node) = self.peek.replace(node) {
494                    o.ignore(Node::new(node))?;
495                }
496
497                break;
498            }
499
500            let span = inner_span(node.span());
501
502            if first.is_none() {
503                first = Some(span);
504            } else {
505                trailing = Some(trailing.map(|head| head.join(span)).unwrap_or(span));
506            }
507
508            if let MaybeNode::Some(old) = out.replace(Node::new(node)) {
509                o.ignore(old)?;
510            }
511
512            count += 1;
513        }
514
515        let span = match (first, &out) {
516            (Some(first), MaybeNode::Some(last)) => first.join(last.span()),
517            _ => self.peek_span(),
518        };
519
520        Ok(Remaining {
521            inside: self.kind(),
522            expected,
523            span,
524            trailing,
525            node: out,
526            count: Some(count),
527        })
528    }
529
530    /// Read one node equal to the given kind.
531    pub(crate) fn one(&mut self, expected: Kind) -> Remaining<'a> {
532        let node = self.eat(expected);
533        let span = node.span().unwrap_or_else(|| self.peek_span());
534        let count = Some(usize::from(node.is_some()));
535
536        Remaining {
537            inside: self.kind(),
538            expected,
539            span,
540            trailing: None,
541            node,
542            count,
543        }
544    }
545
546    /// Require that the iterator is ended.
547    pub(super) fn end(mut self) -> Result<()> {
548        if let Some(node) = self.next_node() {
549            let inside = self.kind();
550
551            let span = match self.iter.next_back() {
552                Some(last) => node.span().join(last.span()),
553                None => *node.span(),
554            };
555
556            return Err(Error::new(
557                inner_span(&span),
558                ErrorKind::ExpectedSyntaxEnd {
559                    inside: inside.into_expectation(),
560                    actual: node.value().into_expectation(),
561                },
562            ));
563        }
564
565        Ok(())
566    }
567
568    /// Get the current span of the parser.
569    pub(crate) fn remaining_span(&mut self) -> Option<Span> {
570        let head = *self.peek_node()?.span();
571
572        if let Some(last) = self.iter.peek_back() {
573            Some(Span::new(head.start, last.span().end))
574        } else {
575            Some(Span::new(head.start, head.end))
576        }
577    }
578
579    pub(crate) fn span(&self) -> Span {
580        inner_span(self.node.span())
581    }
582
583    /// Get the next raw node, including whitespace.
584    #[cfg(feature = "fmt")]
585    pub(crate) fn next_with_ws(&mut self) -> Option<Node<'a>> {
586        if let Some(node) = self.peek.take() {
587            return Some(Node::new(node));
588        }
589
590        self.iter.next().map(Node::new)
591    }
592
593    fn next_node(&mut self) -> Option<InternalNode<'a>> {
594        if let Some(node) = self.peek.take() {
595            return Some(node);
596        }
597
598        // We walk over comments and whitespace separately when writing
599        // nodes to ensure that formatting functions do not need to worry
600        // about it here.
601        self.iter.find(|node| !matches!(node.value(), ws!()))
602    }
603
604    fn next_back_node(&mut self) -> Option<InternalNode<'a>> {
605        // We walk over comments and whitespace separately when writing
606        // nodes to ensure that formatting functions do not need to worry
607        // about it here.
608        if let Some(node) = self.iter.rfind(|node| !matches!(node.value(), ws!())) {
609            return Some(node);
610        }
611
612        self.peek.take()
613    }
614}
615
616impl fmt::Debug for Stream<'_> {
617    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
618        f.debug_struct("Stream").finish_non_exhaustive()
619    }
620}
621
622impl Spanned for Stream<'_> {
623    #[inline]
624    fn span(&self) -> Span {
625        Stream::span(self)
626    }
627}
628
629impl<'a> Iterator for Stream<'a> {
630    type Item = Node<'a>;
631
632    #[inline]
633    fn next(&mut self) -> Option<Self::Item> {
634        self.next_node().map(Node::new)
635    }
636}
637
638impl DoubleEndedIterator for Stream<'_> {
639    #[inline]
640    fn next_back(&mut self) -> Option<Self::Item> {
641        self.next_back_node().map(Node::new)
642    }
643}
644
645/// The identifier of a node.
646#[derive(Debug)]
647pub(crate) struct NodeId(syntree::pointer::PointerUsize);
648
649/// A node associated with a tree.
650#[derive(Debug, TryClone, Clone)]
651#[try_clone(crate)]
652pub(crate) struct NodeAt {
653    tree: Rc<Tree>,
654    #[try_clone(copy)]
655    source_id: SourceId,
656    #[try_clone(copy)]
657    id: syntree::pointer::PointerUsize,
658}
659
660impl NodeAt {
661    /// The tree associated with the node..
662    pub(crate) fn tree(&self) -> &Rc<Tree> {
663        &self.tree
664    }
665
666    /// Parse the node being referenced.
667    pub(crate) fn parse<'a, P, O>(&'a self, parser: P) -> Result<O>
668    where
669        P: FnOnce(&mut Stream<'a>) -> Result<O>,
670    {
671        let Some(node) = self.tree.get(self.id) else {
672            return Err(Error::msg(
673                Span::empty(),
674                try_format!("missing node {}", self.id.get()),
675            ));
676        };
677
678        node.parse(parser)
679    }
680
681    /// Parse a custom id.
682    pub(crate) fn parse_id<'a, P, O>(&'a self, NodeId(id): NodeId, parser: P) -> Result<O>
683    where
684        P: FnOnce(&mut Stream<'a>) -> Result<O>,
685    {
686        let Some(node) = self.tree.get(id) else {
687            return Err(Error::msg(
688                Span::empty(),
689                try_format!("missing node {}", self.id.get()),
690            ));
691        };
692
693        node.parse(parser)
694    }
695
696    /// Print the tree to the given writer.
697    #[cfg(feature = "std")]
698    pub(crate) fn print_with_sources(
699        &self,
700        title: impl fmt::Display,
701        sources: &Sources,
702    ) -> Result<()> {
703        use std::io::Write;
704
705        let o = std::io::stdout();
706        let mut o = o.lock();
707
708        let Some(node) = self.tree.get(self.id) else {
709            return Err(Error::msg(
710                Span::empty(),
711                try_format!("missing node {}", self.id.get()),
712            ));
713        };
714
715        let source = sources.get(self.source_id);
716
717        writeln!(o, "{title}:").with_span(Span::empty())?;
718
719        for (depth, node) in node.inner.walk().with_depths() {
720            if depth < 0 {
721                break;
722            }
723
724            let n = (depth * 2) as usize;
725            let data = node.value();
726            let span = inner_span(node.span());
727
728            if node.has_children() {
729                writeln!(o, "{:n$}{:?}@{}", "", data, span).with_span(span)?;
730            } else if let Some(source) = source.and_then(|s| s.get(span.range())) {
731                writeln!(o, "{:n$}{:?}@{} {:?}", "", data, span, source).with_span(span)?;
732            } else {
733                writeln!(o, "{:n$}{:?}@{} +", "", data, span).with_span(span)?;
734            }
735        }
736
737        Ok(())
738    }
739}
740
741impl Spanned for NodeAt {
742    fn span(&self) -> Span {
743        let Some(node) = self.tree.get(self.id) else {
744            return Span::empty();
745        };
746
747        node.span()
748    }
749}
750
751/// A node being parsed.
752#[derive(Clone)]
753pub(crate) struct Node<'a> {
754    inner: InternalNode<'a>,
755}
756
757impl<'a> Node<'a> {
758    #[inline]
759    pub(super) fn new(inner: InternalNode<'a>) -> Self {
760        Self { inner }
761    }
762
763    /// Check if the current token is empty.
764    pub(crate) fn is_empty(&self) -> bool {
765        self.inner.is_empty()
766    }
767
768    /// Convert a node into a token.
769    pub(crate) fn token(&self) -> Token {
770        inner_token(self.inner)
771    }
772
773    /// Get the kind of the node.
774    pub(crate) fn kind(&self) -> Kind {
775        self.inner.value()
776    }
777
778    /// Walk the subtree.
779    pub(crate) fn walk(&self) -> impl Iterator<Item = Node<'a>> {
780        self.inner.walk().inside().map(Node::new)
781    }
782
783    /// Capture the node at the given position associated with its tree..
784    pub(crate) fn node_at(&self, source_id: SourceId, tree: Rc<Tree>) -> NodeAt {
785        NodeAt {
786            tree,
787            source_id,
788            id: self.inner.id(),
789        }
790    }
791
792    /// Replace the kind of the node.
793    pub(crate) fn replace(&self, kind: Kind) -> Kind {
794        self.inner.replace(kind)
795    }
796
797    /// Iterate over child nodes.
798    pub(crate) fn children(&self) -> impl DoubleEndedIterator<Item = Node<'a>> + '_ {
799        self.inner.children().map(Node::new)
800    }
801
802    /// Iterate over child nodes using the internal iterator.
803    pub(crate) fn internal_children(&self) -> InternalChildren<'a> {
804        self.inner.children()
805    }
806
807    /// Get the children as a fixed array ignoring whitespace.
808    pub(crate) fn fixed_vec<const N: usize, T>(
809        &self,
810        factory: fn(InternalNode<'a>) -> T,
811    ) -> Option<FixedVec<T, N>> {
812        let mut vec = FixedVec::new();
813
814        for node in self
815            .inner
816            .children()
817            .filter(|n| !matches!(n.value(), ws!()))
818        {
819            if vec.try_push(factory(node)).is_err() {
820                return None;
821            }
822        }
823
824        Some(vec)
825    }
826
827    /// Get the kinds of all children excluding whitespace.
828    pub(crate) fn kinds<const N: usize>(&self) -> Option<[Kind; N]> {
829        self.fixed_vec(|n| n.value())?.try_into_inner()
830    }
831
832    /// Get the tokens of all children excluding whitespace.
833    pub(crate) fn tokens<const N: usize>(&self) -> Option<FixedVec<Token, N>> {
834        self.fixed_vec(inner_token)
835    }
836
837    /// Get the children as an array ignoring whitespace.
838    pub(crate) fn nodes<const N: usize>(&self) -> Option<[Node<'a>; N]> {
839        self.fixed_vec(Node::new)?.try_into_inner()
840    }
841
842    /// Helper to coerce a node into an ast element.
843    pub(crate) fn ast<T>(self) -> Result<T>
844    where
845        T: ToAst,
846    {
847        T::to_ast(self.span(), self.kind())
848    }
849
850    /// Construct an unsupported error.
851    #[cfg(feature = "fmt")]
852    pub(crate) fn unsupported(&self, expected: impl IntoExpectation) -> Error {
853        Error::new(
854            self.span(),
855            ErrorKind::ExpectedSyntax {
856                expected: expected.into_expectation(),
857                actual: self.kind().into_expectation(),
858            },
859        )
860    }
861
862    /// Write the remaining token, or fallback to the given literal if unavailable.
863    #[cfg(feature = "fmt")]
864    pub(crate) fn fmt(self, o: &mut Formatter<'a>) -> Result<()> {
865        o.write_owned(self)
866    }
867
868    /// Ignore the node.
869    #[cfg(feature = "fmt")]
870    pub(crate) fn ignore(self, o: &mut Formatter<'a>) -> Result<()> {
871        o.ignore(self)
872    }
873
874    /// Walk from the current node.
875    #[cfg(feature = "fmt")]
876    pub(crate) fn walk_from(&self) -> impl Iterator<Item = Node<'a>> + '_ {
877        self.inner.walk_from().map(Node::new)
878    }
879
880    /// Run the given parser.
881    #[inline]
882    pub(crate) fn parse<P, O>(self, parser: P) -> Result<O>
883    where
884        P: FnOnce(&mut Stream<'a>) -> Result<O>,
885    {
886        self.into_stream().parse(parser)
887    }
888
889    /// Convert into a stream.
890    pub(crate) fn into_stream(self) -> StreamBuf<'a> {
891        StreamBuf {
892            stream: Stream::new(self.inner),
893        }
894    }
895
896    /// Construct a span for the current node.
897    pub(crate) fn span(&self) -> Span {
898        inner_span(self.inner.span())
899    }
900
901    /// Test if the current node is whitespace.
902    #[cfg(feature = "fmt")]
903    pub(crate) fn is_whitespace(&self) -> bool {
904        matches!(self.inner.value(), Kind::Whitespace)
905    }
906
907    /// Test if the node has children.
908    #[cfg(feature = "fmt")]
909    pub(crate) fn has_children(&self) -> bool {
910        self.inner.has_children()
911    }
912
913    /// Find a node which matches the given kind.
914    pub(crate) fn find(&self, kind: Kind) -> Option<Node<'a>> {
915        self.inner
916            .children()
917            .find(|n| n.value() == kind)
918            .map(Node::new)
919    }
920
921    /// Report an unsupported error for the current node.
922    pub(crate) fn expected(&self, expected: impl IntoExpectation) -> Error {
923        Error::new(
924            self.span(),
925            ErrorKind::ExpectedSyntax {
926                expected: expected.into_expectation(),
927                actual: self.kind().into_expectation(),
928            },
929        )
930    }
931}
932
933#[inline]
934pub(super) fn inner_token(node: InternalNode<'_>) -> Token {
935    Token {
936        span: inner_span(node.span()),
937        kind: node.value(),
938    }
939}
940
941#[inline]
942fn inner_span(span: &syntree::Span<u32>) -> Span {
943    Span::new(span.start, span.end)
944}
945
946impl IntoExpectation for Node<'_> {
947    #[inline]
948    fn into_expectation(self) -> Expectation {
949        self.inner.value().into_expectation()
950    }
951}
952
953impl Spanned for Node<'_> {
954    #[inline]
955    fn span(&self) -> Span {
956        Node::span(self)
957    }
958}
959
960impl fmt::Debug for Node<'_> {
961    #[inline]
962    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
963        f.debug_struct("Node")
964            .field("kind", &self.kind())
965            .field("span", &self.span())
966            .finish()
967    }
968}
969
970#[must_use = "Remaining nodes must be consumed to capture all whitespace and comments"]
971pub(crate) struct Remaining<'a> {
972    inside: Kind,
973    expected: Kind,
974    span: Span,
975    /// If there is more than one element, this contains the trailing span.
976    trailing: Option<Span>,
977    node: MaybeNode<'a>,
978    count: Option<usize>,
979}
980
981impl<'a> Remaining<'a> {
982    /// Get trailing span.
983    pub(crate) fn trailing(&self) -> Option<Span> {
984        self.trailing
985    }
986
987    /// Ensure that there is exactly one node represented by this container.
988    ///
989    /// This only fires if the remaining set has been constructed from a stream.
990    pub(crate) fn exactly_one(self, o: &mut dyn Ignore<'a>) -> Result<()> {
991        if let MaybeNode::Some(node) = self.node {
992            o.ignore(node)?;
993        }
994
995        let Some(count) = self.count else {
996            return Ok(());
997        };
998
999        if count == 0 {
1000            let result = o.error(Error::new(
1001                self.span,
1002                ErrorKind::ExpectedOne {
1003                    inside: self.inside.into_expectation(),
1004                    expected: self.expected.into_expectation(),
1005                },
1006            ));
1007
1008            result.with_span(self.span)?;
1009        }
1010
1011        if let Some(span) = self.trailing {
1012            let result = o.error(Error::new(
1013                span,
1014                ErrorKind::ExpectedAtMostOne {
1015                    inside: self.inside.into_expectation(),
1016                    expected: self.expected.into_expectation(),
1017                    count,
1018                },
1019            ));
1020
1021            result.with_span(self.span)?;
1022        }
1023
1024        Ok(())
1025    }
1026
1027    /// Ensure that there are at most one node represented by this container.
1028    ///
1029    /// This only fires if the remaining set has been constructed from a stream.
1030    pub(crate) fn at_most_one(self, o: &mut dyn Ignore<'a>) -> Result<()> {
1031        if let MaybeNode::Some(node) = self.node {
1032            o.ignore(node)?;
1033        }
1034
1035        let Some(count) = self.count else {
1036            return Ok(());
1037        };
1038
1039        if let Some(span) = self.trailing {
1040            let result = o.error(Error::new(
1041                span,
1042                ErrorKind::ExpectedAtMostOne {
1043                    inside: self.inside.into_expectation(),
1044                    expected: self.expected.into_expectation(),
1045                    count,
1046                },
1047            ));
1048
1049            result.with_span(self.span)?;
1050        }
1051
1052        Ok(())
1053    }
1054
1055    /// Ensure that there are at least one node represented by this container.
1056    ///
1057    /// This only fires if the remaining set has been constructed from a stream.
1058    pub(crate) fn at_least_one(self, o: &mut dyn Ignore<'a>) -> Result<()> {
1059        if let MaybeNode::Some(node) = self.node {
1060            o.ignore(node)?;
1061        }
1062
1063        if matches!(self.count, Some(0)) {
1064            let result = o.error(Error::new(
1065                self.span,
1066                ErrorKind::ExpectedAtLeastOne {
1067                    inside: self.inside.into_expectation(),
1068                    expected: self.expected.into_expectation(),
1069                },
1070            ));
1071
1072            result.with_span(self.span)?;
1073        }
1074
1075        Ok(())
1076    }
1077
1078    /// Test if there is a remaining node present.
1079    #[inline]
1080    pub(crate) fn is_present(&self) -> bool {
1081        self.node.is_some()
1082    }
1083
1084    #[inline]
1085    pub(crate) fn is_absent(&self) -> bool {
1086        self.node.is_none()
1087    }
1088
1089    /// Write the remaining token, or fallback to the given literal if unavailable.
1090    #[cfg(feature = "fmt")]
1091    pub(crate) fn fmt(self, o: &mut Formatter<'a>) -> Result<bool> {
1092        self.write_if(o, true)
1093    }
1094
1095    /// Write the remaining token, or fallback to the given literal if
1096    /// unavailable and needed.
1097    #[cfg(feature = "fmt")]
1098    pub(crate) fn write_if(mut self, o: &mut Formatter<'a>, needed: bool) -> Result<bool> {
1099        if self.count.is_none() {
1100            return Ok(false);
1101        }
1102
1103        if let MaybeNode::Some(node) = self.node.take() {
1104            o.write_owned(node)?;
1105        } else if needed {
1106            o.lit(self.lit()?)?;
1107        }
1108
1109        Ok(true)
1110    }
1111
1112    /// Write the remaining token, or fallback to the given literal if
1113    /// unavailable and even then only if it's needed.
1114    #[cfg(feature = "fmt")]
1115    pub(crate) fn write_only_if(mut self, o: &mut Formatter<'a>, needed: bool) -> Result<()> {
1116        if let MaybeNode::Some(node) = self.node.take() {
1117            if needed {
1118                o.write_owned(node)?;
1119            } else {
1120                o.ignore(node)?;
1121            }
1122        } else if needed {
1123            o.lit(self.lit()?)?;
1124        }
1125
1126        Ok(())
1127    }
1128
1129    /// Ignore the remaining token.
1130    pub(crate) fn ignore(self, o: &mut dyn Ignore<'a>) -> Result<bool> {
1131        if self.count.is_none() {
1132            return Ok(false);
1133        }
1134
1135        if let MaybeNode::Some(node) = self.node {
1136            o.ignore(node)?;
1137        }
1138
1139        Ok(true)
1140    }
1141
1142    #[cfg(feature = "fmt")]
1143    fn lit(&self) -> Result<&'static str> {
1144        let lit = match self.expected.into_expectation() {
1145            Expectation::Keyword(lit) => lit,
1146            Expectation::Delimiter(lit) => lit,
1147            Expectation::Punctuation(lit) => lit,
1148            expectation => {
1149                return Err(Error::new(
1150                    self.span,
1151                    ErrorKind::UnsupportedDelimiter { expectation },
1152                ));
1153            }
1154        };
1155
1156        Ok(lit)
1157    }
1158}
1159
1160impl Default for Remaining<'_> {
1161    #[inline]
1162    fn default() -> Self {
1163        Self {
1164            inside: Kind::Root,
1165            expected: Kind::Eof,
1166            span: Span::empty(),
1167            trailing: None,
1168            node: MaybeNode::None,
1169            count: None,
1170        }
1171    }
1172}
1173
1174#[derive(Default, Clone)]
1175struct Iter<'a> {
1176    first: Option<InternalNode<'a>>,
1177    last: Option<InternalNode<'a>>,
1178}
1179
1180impl<'a> Iter<'a> {
1181    fn new(first: Option<InternalNode<'a>>, last: Option<InternalNode<'a>>) -> Self {
1182        Self { first, last }
1183    }
1184
1185    /// Peek the next back node.
1186    fn peek_back(&self) -> Option<InternalNode<'a>> {
1187        self.last
1188    }
1189}
1190
1191impl<'a> Iterator for Iter<'a> {
1192    type Item = InternalNode<'a>;
1193
1194    fn next(&mut self) -> Option<Self::Item> {
1195        let node = self.first.take()?;
1196
1197        if Some(node.id()) == self.last.map(|n| n.id()) {
1198            self.last = None;
1199        } else {
1200            self.first = node.next();
1201        }
1202
1203        Some(node)
1204    }
1205}
1206
1207impl DoubleEndedIterator for Iter<'_> {
1208    fn next_back(&mut self) -> Option<Self::Item> {
1209        let node = self.last.take()?;
1210
1211        if Some(node.id()) == self.first.map(|n| n.id()) {
1212            self.first = None;
1213        } else {
1214            self.last = node.prev();
1215        }
1216
1217        Some(node)
1218    }
1219}
1220
1221/// Maybe a node.
1222#[derive(Default)]
1223pub(crate) enum MaybeNode<'a> {
1224    Some(Node<'a>),
1225    #[default]
1226    None,
1227}
1228
1229impl<'a> MaybeNode<'a> {
1230    /// Test if the node is set.
1231    pub(crate) fn is_some(&self) -> bool {
1232        matches!(self, MaybeNode::Some(..))
1233    }
1234
1235    /// Test if the node is not set.
1236    pub(crate) fn is_none(&self) -> bool {
1237        matches!(self, MaybeNode::None)
1238    }
1239
1240    /// Format the node if present.
1241    #[cfg(feature = "fmt")]
1242    pub(crate) fn fmt(self, o: &mut Formatter<'a>) -> Result<()> {
1243        match self {
1244            MaybeNode::Some(node) => node.fmt(o),
1245            MaybeNode::None => Ok(()),
1246        }
1247    }
1248
1249    /// Map the result.
1250    #[cfg(feature = "fmt")]
1251    pub(crate) fn and_then<O>(self, f: impl FnOnce(Node<'a>) -> Result<O>) -> Result<Option<O>> {
1252        match self {
1253            MaybeNode::Some(node) => Ok(Some(f(node)?)),
1254            MaybeNode::None => Ok(None),
1255        }
1256    }
1257
1258    /// Take the interior value of present.
1259    #[cfg(feature = "fmt")]
1260    pub(crate) fn take(&mut self) -> Self {
1261        take(self)
1262    }
1263
1264    /// Replace the interior value if present.
1265    pub(crate) fn replace(&mut self, node: Node<'a>) -> Self {
1266        replace(self, MaybeNode::Some(node))
1267    }
1268
1269    /// Get the span of the underlying node.
1270    pub(crate) fn span(&self) -> Option<Span> {
1271        match self {
1272            MaybeNode::Some(node) => Some(node.span()),
1273            MaybeNode::None => None,
1274        }
1275    }
1276
1277    /// Helper to coerce a node into an ast element.
1278    pub(crate) fn ast<T>(self) -> Result<Option<T>>
1279    where
1280        T: ToAst,
1281    {
1282        match self {
1283            MaybeNode::Some(node) => node.ast().map(Some),
1284            MaybeNode::None => Ok(None),
1285        }
1286    }
1287
1288    /// Parse the node being referenced.
1289    pub(crate) fn parse<P, O>(self, parser: P) -> Result<Option<O>>
1290    where
1291        P: FnOnce(&mut Stream<'a>) -> Result<O>,
1292    {
1293        match self {
1294            MaybeNode::Some(node) => node.parse(parser).map(Some),
1295            MaybeNode::None => Ok(None),
1296        }
1297    }
1298}
rune/grammar/tree.rs

rune/grammar/
tree.rs
