regast-core 0.1.0

Parse-tree matching backends for regast
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

use crate::{IrId, IrKind, IrPool};

#[cfg(test)]
pub fn deriv(pool: &mut IrPool, root: IrId, c: char) -> IrId {
    deriv_at(pool, root, c, 1, 2)
}

pub fn deriv_at(pool: &mut IrPool, root: IrId, c: char, position: usize, input_len: usize) -> IrId {
    let key = (root, c, position == 0, position == input_len);
    if let Some(id) = pool.deriv_memo.get(&key) {
        return *id;
    }
    let kind = pool.kind(root).clone();
    let result = match kind {
        IrKind::Zero | IrKind::One | IrKind::Anchor(..) => pool.zero(),
        IrKind::Class(set, _) => {
            if pool.get_class_set(set).contains(c) {
                pool.one()
            } else {
                pool.zero()
            }
        }
        IrKind::Alt(left, right, prov, ordered) => {
            let left = deriv_at(pool, left, c, position, input_len);
            let right = deriv_at(pool, right, c, position, input_len);
            pool.alt(left, right, prov, ordered)
        }
        IrKind::Seq(left, right, prov) => {
            let left_deriv = deriv_at(pool, left, c, position, input_len);
            let sequence = pool.seq(left_deriv, right, prov);
            if nullable_at(pool, left, position, input_len) {
                let right_deriv = deriv_at(pool, right, c, position, input_len);
                if pool.prefers_empty(left) {
                    pool.alt(right_deriv, sequence, prov, false)
                } else {
                    pool.alt(sequence, right_deriv, prov, false)
                }
            } else {
                sequence
            }
        }
        IrKind::Star(inner, prov, _) => {
            let derivative = deriv_at(pool, inner, c, position, input_len);
            pool.seq(derivative, root, prov)
        }
    };
    pool.deriv_memo.insert(key, result);
    result
}

pub fn nullable_at(pool: &mut IrPool, root: IrId, position: usize, input_len: usize) -> bool {
    match pool.kind(root).clone() {
        IrKind::Zero | IrKind::Class(..) => false,
        IrKind::One | IrKind::Star(..) => true,
        IrKind::Anchor(regast_syntax::AnchorKind::Start, _) => position == 0,
        IrKind::Anchor(regast_syntax::AnchorKind::End, _) => position == input_len,
        IrKind::Alt(left, right, _, _) => {
            nullable_at(pool, left, position, input_len)
                || nullable_at(pool, right, position, input_len)
        }
        IrKind::Seq(left, right, _) => {
            nullable_at(pool, left, position, input_len)
                && nullable_at(pool, right, position, input_len)
        }
    }
}

#[cfg(test)]
mod tests {
    use regast_syntax::ClassSet;

    use super::*;
    use crate::Prov;

    #[test]
    fn derivative_definitions_hold_for_atoms_and_star() {
        let mut pool = IrPool::new();
        let set_id = pool.class_set(ClassSet::singleton('a'));
        let atom = pool.class(set_id, Prov::Synth(regast_syntax::NodeId(0)));
        assert_eq!(deriv(&mut pool, atom, 'a'), pool.one());
        assert_eq!(deriv(&mut pool, atom, 'b'), pool.zero());
        let star = pool.star(atom, Prov::Synth(regast_syntax::NodeId(0)), true);
        let derivative = deriv(&mut pool, star, 'a');
        assert!(matches!(pool.kind(derivative), IrKind::Seq(_, id, _) if *id == star));
    }
}