sipha 3.0.0

PEG parser, syntax trees, and code generation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

//! # Capture Tree
//!
//! Transforms the flat [`CaptureEvent`] log produced by the VM into a
//! typed, tree-structured output that callers can traverse.

use crate::types::{CaptureEvent, Pos, Span, Tag};
#[cfg(not(feature = "std"))]
use alloc::vec::Vec;
#[cfg(feature = "std")]
use std::vec::Vec;

/// A node in the capture tree.
#[derive(Clone, Debug)]
pub struct CaptureNode {
    pub tag: Tag,
    pub span: Span,
    pub children: Vec<Self>,
}

impl CaptureNode {
    /// Build a forest of [`CaptureNode`]s from the flat event log.
    ///
    /// Events form a well-nested sequence of `Open`/`Close` pairs.
    /// Returns the top-level nodes (may be multiple if the grammar emits
    /// sibling captures at the root level).
    ///
    /// # Panics
    ///
    /// Panics if `events` has a `Close` without a matching `Open`, or if
    /// unclosed regions remain at the end (debug builds only for the latter).
    #[must_use]
    pub fn build_forest(events: &[CaptureEvent]) -> Vec<Self> {
        let mut stack: Vec<(Tag, Pos, Vec<Self>)> = Vec::new();
        let mut roots: Vec<Self> = Vec::new();

        for &ev in events {
            match ev {
                CaptureEvent::Open { tag, pos } => {
                    stack.push((tag, pos, Vec::new()));
                }
                CaptureEvent::Close { tag, pos } => {
                    let (open_tag, start, children) = stack
                        .pop()
                        .expect("capture event mismatch: Close without Open");
                    debug_assert_eq!(open_tag, tag, "mismatched capture tags");
                    let node = Self {
                        tag,
                        span: Span::new(start, pos),
                        children,
                    };
                    match stack.last_mut() {
                        Some((_, _, parent_children)) => parent_children.push(node),
                        None => roots.push(node),
                    }
                }
            }
        }

        debug_assert!(stack.is_empty(), "unclosed capture regions");
        roots
    }

    /// Convenience: extract the text of this node from the input buffer.
    #[must_use]
    #[inline]
    pub fn text<'a>(&self, input: &'a [u8]) -> &'a [u8] {
        self.span.as_slice(input)
    }

    /// Depth-first traversal, calling `f` on every node.
    pub fn walk(&self, f: &mut impl FnMut(&Self)) {
        f(self);
        for child in &self.children {
            child.walk(f);
        }
    }

    /// Find the first descendant (or self) with the given `tag`.
    #[must_use]
    pub fn find(&self, tag: Tag) -> Option<&Self> {
        if self.tag == tag {
            return Some(self);
        }
        self.children.iter().find_map(|c| c.find(tag))
    }

    /// Collect all descendants (including self) with the given `tag`.
    #[must_use]
    pub fn find_all(&self, tag: Tag) -> Vec<&Self> {
        let mut result = Vec::new();
        self.collect_all(tag, &mut result);
        result
    }

    fn collect_all<'a>(&'a self, tag: Tag, out: &mut Vec<&'a Self>) {
        if self.tag == tag {
            out.push(self);
        }
        for child in &self.children {
            child.collect_all(tag, out);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn build_forest_single_node() {
        let events = [
            CaptureEvent::Open { tag: 1, pos: 0 },
            CaptureEvent::Close { tag: 1, pos: 5 },
        ];
        let forest = CaptureNode::build_forest(&events);
        assert_eq!(forest.len(), 1);
        assert_eq!(forest[0].tag, 1);
        assert_eq!(forest[0].span.start, 0);
        assert_eq!(forest[0].span.end, 5);
        assert!(forest[0].children.is_empty());
    }

    #[test]
    fn build_forest_nested() {
        let events = [
            CaptureEvent::Open { tag: 0, pos: 0 },
            CaptureEvent::Open { tag: 1, pos: 1 },
            CaptureEvent::Close { tag: 1, pos: 4 },
            CaptureEvent::Close { tag: 0, pos: 5 },
        ];
        let forest = CaptureNode::build_forest(&events);
        assert_eq!(forest.len(), 1);
        assert_eq!(forest[0].tag, 0);
        assert_eq!(forest[0].children.len(), 1);
        assert_eq!(forest[0].children[0].tag, 1);
        assert_eq!(forest[0].children[0].span.start, 1);
        assert_eq!(forest[0].children[0].span.end, 4);
    }

    #[test]
    fn capture_node_text() {
        let events = [
            CaptureEvent::Open { tag: 0, pos: 2 },
            CaptureEvent::Close { tag: 0, pos: 7 },
        ];
        let forest = CaptureNode::build_forest(&events);
        let input = b"hello world";
        assert_eq!(forest[0].text(input), b"llo w");
    }
}