pink-runtime 0.1.1

A very minimal replecement based DSL, intended for math.
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

#[cfg(test)]
mod test;

use std::collections::BTreeMap;

use crate::engine::{PatternToken, Token};

type SingleBindings<'a, 'b> = BTreeMap<&'a String, &'b Token>;
type SpreadBindings<'a, 'b> = BTreeMap<&'a String, &'b [Token]>;

type Bindings<'a, 'b> = (SingleBindings<'a, 'b>, SpreadBindings<'a, 'b>);

pub fn get_match_bindings<'a, 'b>(
    pattern: &'a [PatternToken],
    expression: &'b [Token],
) -> Option<Bindings<'a, 'b>> {
    let mut single_bindings = BTreeMap::new();
    let mut spread_bindings = BTreeMap::new();

    match_bindings_recurse(
        pattern,
        expression,
        &mut single_bindings,
        &mut spread_bindings,
    )?;

    Some((single_bindings, spread_bindings))
}

fn match_bindings_recurse<'a, 'b>(
    pattern: &'a [PatternToken],
    expression: &'b [Token],
    single_bindings: &mut SingleBindings<'a, 'b>,
    spread_bindings: &mut SpreadBindings<'a, 'b>,
) -> Option<()> {
    let (pattern_token, token) = match (pattern.get(0), expression.get(0)) {
        (Some(pattern_token), Some(token)) => (pattern_token, token),
        (None, None) => return Some(()),
        _ => return None,
    };

    match pattern_token {
        PatternToken::Concrete(pattern_token) => {
            if pattern_token == token {
                match_bindings_recurse(
                    &pattern[1..],
                    &expression[1..],
                    single_bindings,
                    spread_bindings,
                )
            } else {
                None
            }
        }

        PatternToken::Variable(variable) => match single_bindings.get(variable) {
            Some(existing_binding) => {
                if existing_binding == &token {
                    match_bindings_recurse(
                        &pattern[1..],
                        &expression[1..],
                        single_bindings,
                        spread_bindings,
                    )
                } else {
                    None
                }
            }
            None => {
                single_bindings.insert(variable, token);
                match_bindings_recurse(
                    &pattern[1..],
                    &expression[1..],
                    single_bindings,
                    spread_bindings,
                )
            }
        },

        PatternToken::SpreadVariable(variable) => {
            for i in 1..=expression.len() {
                let binding = &expression[0..i];

                match spread_bindings.get(variable) {
                    Some(existing_binding) => {
                        if existing_binding == &binding
                            && match_bindings_recurse(
                                &pattern[1..],
                                &expression[i..],
                                single_bindings,
                                spread_bindings,
                            )
                            .is_some()
                        {
                            return Some(());
                        };
                    }
                    None => {
                        // TODO: It is kind of ugly to remove and add a binding each time but I'm not sure it can be done in a better way.
                        // It kind of seems this is the reason the pure recursive approach didn't work in the first place.
                        // The fact that without this the only test that failed is the one that failed with the recursive approach,
                        // this makes me think that this is the reason.
                        spread_bindings.insert(variable, binding);

                        if match_bindings_recurse(
                            &pattern[1..],
                            &expression[i..],
                            single_bindings,
                            spread_bindings,
                        )
                        .is_some()
                        {
                            return Some(());
                        }

                        spread_bindings.remove(variable);
                    }
                }
            }

            None
        }
    }
}