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
use crate::classic::clvm::__type_compatibility__::{Bytes, BytesFromType};
use crate::classic::clvm::sexp::equal_to;
use clvm_rs::allocator::{Allocator, NodePtr, SExp};
use std::collections::HashMap;
pub const ATOM_MATCH: [u8; 1] = [b'$'];
pub const SEXP_MATCH: [u8; 1] = [b':'];
pub fn unify_bindings(
allocator: &mut Allocator,
bindings: HashMap<String, NodePtr>,
new_key: &[u8],
new_value: NodePtr,
) -> Option<HashMap<String, NodePtr>> {
/*
* Try to add a new binding to the list, rejecting it if it conflicts
* with an existing binding.
*/
let new_key_str = Bytes::new(Some(BytesFromType::Raw(new_key.to_vec()))).decode();
match bindings.get(&new_key_str) {
Some(binding) => {
if !equal_to(allocator, *binding, new_value) {
return None;
}
Some(bindings)
}
_ => {
let mut new_bindings = bindings.clone();
new_bindings.insert(new_key_str, new_value);
Some(new_bindings)
}
}
}
pub fn match_sexp(
allocator: &mut Allocator,
pattern: NodePtr,
sexp: NodePtr,
known_bindings: HashMap<String, NodePtr>,
) -> Option<HashMap<String, NodePtr>> {
/*
* Determine if sexp matches the pattern, with the given known bindings already applied.
* Returns None if no match, or a (possibly empty) dictionary of bindings if there is a match
* Patterns look like this:
* ($ . $) matches the literal "$", no bindings (mostly useless)
* (: . :) matches the literal ":", no bindings (mostly useless)
* ($ . A) matches B if B is an atom; and A is bound to B
* (: . A) matches B always; and A is bound to B
* (A . B) matches (C . D) if A matches C and B matches D
* and bindings are the unification (as long as unification is possible)
*/
match (allocator.sexp(pattern), allocator.sexp(sexp)) {
(SExp::Atom, SExp::Atom) => {
// Two nodes in scope, both used.
if allocator.atom(pattern) == allocator.atom(sexp) {
Some(known_bindings)
} else {
None
}
}
(SExp::Pair(pleft, pright), _) => match (allocator.sexp(pleft), allocator.sexp(pright)) {
(SExp::Atom, SExp::Atom) => {
let left_atom = allocator.atom(pleft);
let right_atom = allocator.atom(pright);
// This is a false positive due to Allocator lifetime.
#[allow(clippy::unnecessary_to_owned)]
match allocator.sexp(sexp) {
SExp::Atom => {
// Expression is ($ . $), sexp is '$', result: no capture.
// Avoid double borrow.
let sexp_atom = allocator.atom(sexp);
if left_atom.as_ref() == ATOM_MATCH {
if right_atom.as_ref() == ATOM_MATCH {
if sexp_atom.as_ref() == ATOM_MATCH {
return Some(HashMap::new());
}
return None;
}
return unify_bindings(
allocator,
known_bindings,
&right_atom.as_ref().to_vec(),
sexp,
);
}
if left_atom.as_ref() == SEXP_MATCH {
if right_atom.as_ref() == SEXP_MATCH && sexp_atom.as_ref() == SEXP_MATCH
{
return Some(HashMap::new());
}
return unify_bindings(
allocator,
known_bindings,
// pat_right_bytes
&right_atom.as_ref().to_vec(),
sexp,
);
}
None
}
SExp::Pair(sleft, sright) => {
if left_atom.as_ref() == SEXP_MATCH && right_atom.as_ref() != SEXP_MATCH {
return unify_bindings(
allocator,
known_bindings,
// pat_right_bytes
&right_atom.as_ref().to_vec(),
sexp,
);
}
match_sexp(allocator, pleft, sleft, known_bindings).and_then(
|new_bindings| match_sexp(allocator, pright, sright, new_bindings),
)
}
}
}
_ => match allocator.sexp(sexp) {
SExp::Atom => None,
SExp::Pair(sleft, sright) => match_sexp(allocator, pleft, sleft, known_bindings)
.and_then(|new_bindings| match_sexp(allocator, pright, sright, new_bindings)),
},
},
(SExp::Atom, _) => None,
}
}