regast-syntax 0.1.0

Lossless syntax tree for the regast regular expression engine
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

use crate::{Cursor, Pattern};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Flow {
    Continue,
    SkipChildren,
}

pub trait Visitor {
    type Output;
    type Err;

    /// Called before visiting a node's children.
    ///
    /// # Errors
    ///
    /// Implementations may return their visitor-specific error.
    fn enter(&mut self, _node: Cursor<'_>) -> Result<Flow, Self::Err> {
        Ok(Flow::Continue)
    }

    /// Called after visiting a node's children.
    ///
    /// # Errors
    ///
    /// Implementations may return their visitor-specific error.
    fn leave(&mut self, _node: Cursor<'_>) -> Result<(), Self::Err> {
        Ok(())
    }

    /// Consume the visitor and return its output.
    ///
    /// # Errors
    ///
    /// Implementations may return their visitor-specific error.
    fn finish(self) -> Result<Self::Output, Self::Err>;
}

/// Walk `pattern` without recursion and drive `visitor`.
///
/// # Errors
///
/// Returns the first error reported by `visitor`.
pub fn visit<V: Visitor>(pattern: &Pattern, mut visitor: V) -> Result<V::Output, V::Err> {
    let mut stack = vec![(pattern.root(), false)];
    while let Some((node, leaving)) = stack.pop() {
        if leaving {
            visitor.leave(node)?;
            continue;
        }
        let flow = visitor.enter(node)?;
        stack.push((node, true));
        if flow == Flow::Continue {
            stack.extend(node.children().rev().map(|child| (child, false)));
        }
    }
    visitor.finish()
}

#[cfg(test)]
mod tests {
    use std::convert::Infallible;

    use crate::Pattern;

    use super::*;

    struct Recorder(Vec<String>);

    impl Visitor for Recorder {
        type Output = Vec<String>;
        type Err = Infallible;

        fn enter(&mut self, node: Cursor<'_>) -> Result<Flow, Self::Err> {
            self.0.push(format!("+{}", node.text()));
            Ok(Flow::Continue)
        }

        fn leave(&mut self, node: Cursor<'_>) -> Result<(), Self::Err> {
            self.0.push(format!("-{}", node.text()));
            Ok(())
        }

        fn finish(self) -> Result<Self::Output, Self::Err> {
            Ok(self.0)
        }
    }

    #[test]
    fn drives_enter_and_leave_without_recursion() {
        let pattern = Pattern::parse("ab|c").unwrap();
        let events = visit(&pattern, Recorder(Vec::new())).unwrap();
        assert_eq!(events.first().unwrap(), "+ab|c");
        assert_eq!(events.last().unwrap(), "-ab|c");
        assert_eq!(events.len(), pattern.len() * 2);

        let first_leaf = pattern
            .root()
            .walk()
            .find(|node| node.text() == "a")
            .unwrap();
        assert_eq!(first_leaf.ancestors().next().unwrap().text(), "ab");
        assert_eq!(first_leaf.next_sibling().unwrap().text(), "b");
    }
}