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
|
use std::collections::HashMap;
use crate::sexpr::{Atom, Expr, Variable, VariableType};
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum BindValue {
Integer(i64),
Expr(Expr),
Ellipsis(Vec<Expr>)
}
#[derive(Default)]
pub struct Bindings<'b>(HashMap<&'b str, BindValue>);
impl<'b> Bindings<'b> {
pub fn check_or_insert(&mut self, index: &'b String, bind_value: BindValue) -> bool {
if let Some(existing) = self.0.get(index.as_str()) {
existing == &bind_value
} else {
self.0.insert(index, bind_value);
true
}
}
}
impl std::fmt::Debug for Bindings<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{:?}", self.0)
}
}
pub fn args_match<'b>(p_args: &'b [Expr], args: &'b [Expr], bindings: &mut Bindings<'b>) -> bool {
const ELLIPSIS: Expr = Expr::Atom(Atom::Ellipsis);
if p_args.contains(&ELLIPSIS) {
let mut sorted_p: Vec<&Expr> = p_args.iter()
.filter(|p| **p != ELLIPSIS)
.collect();
let mut sorted_a: Vec<&Expr> = args.iter().collect();
if sorted_p.len() != sorted_a.len() {
return false;
}
sorted_p.sort();
sorted_a.sort();
std::iter::zip(sorted_p, sorted_a).all(|(p, a)| {
matches(p, a, bindings)
})
} else {
if p_args.len() != args.len() {
return false;
}
std::iter::zip(p_args.iter(), args.iter()).all(|(a, b)| {
matches(a, b, bindings)
})
}
}
pub fn matches<'b>(p: &'b Expr, expr: &'b Expr, bindings: &mut Bindings<'b>) -> bool {
match expr {
Expr::Atom(Atom::Int(i)) => {
match p {
Expr::Atom(Atom::Int(pi)) => i == pi,
Expr::Atom(Atom::Variable(Variable { r#type: e @ (VariableType::Integer | VariableType::Expr), index })) => {
bindings.check_or_insert(index, match e {
VariableType::Integer => BindValue::Integer(*i),
VariableType::Expr => BindValue::Expr(Expr::Atom(Atom::Int(*i)))
})
}
_ => false
}
}
Expr::Atom(Atom::Builtin(s)) => {
match p {
Expr::Atom(Atom::Builtin(ps)) => s == ps,
Expr::Atom(Atom::Variable(Variable { r#type: VariableType::Expr, index })) => {
bindings.check_or_insert(index, BindValue::Expr(Expr::Atom(Atom::Builtin(s.to_string()))))
}
_ => false
}
}
Expr::Application(exprs) => {
if let Expr::Atom(Atom::Builtin(f)) = &exprs[0] &&
let Expr::Application(p_exprs) = p &&
let Expr::Atom(Atom::Builtin(pf)) = &p_exprs[0] {
f == pf && args_match(&p_exprs[1..], &exprs[1..], bindings)
} else if exprs.len() == 1 {
matches(p, &exprs[0], bindings)
} else if let Expr::Atom(Atom::Variable(Variable { r#type: VariableType::Expr, index })) = p {
bindings.check_or_insert(index, BindValue::Expr(expr.clone()))
} else {
false
}
},
Expr::Atom(Atom::Variable(_)) | Expr::Atom(Atom::Ellipsis) => {
// These should only appear in patterns, not in expressions being matched
false
}
}
}
|
