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
|
use std::collections::HashMap;
use crate::syntax::{Label, V};
/// Stores an alpha-normalized variable.
#[derive(Clone, Eq)]
pub struct AlphaVar {
alpha: V<()>,
}
// Exactly like a Label, but equality returns always true.
// This is so that ValueKind equality is exactly alpha-equivalence.
#[derive(Clone, Eq)]
pub struct Binder {
name: Label,
}
impl AlphaVar {
pub(crate) fn idx(&self) -> usize {
self.alpha.idx()
}
pub(crate) fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
Some(AlphaVar {
alpha: self.alpha.shift(delta, &var.alpha)?,
})
}
pub(crate) fn under_binder<T>(&self, x: T) -> Self
where
T: Into<AlphaVar>,
{
// Can't fail since delta is positive
self.shift(1, &x.into()).unwrap()
}
pub(crate) fn over_binder(&self, x: &AlphaVar) -> Option<Self> {
self.shift(-1, x)
}
pub(crate) fn under_multiple_binders(
&self,
shift_map: &HashMap<Label, usize>,
) -> Self {
AlphaVar {
alpha: self.alpha.under_multiple_binders(shift_map),
}
}
}
impl Binder {
pub(crate) fn new(name: Label) -> Self {
Binder { name }
}
pub(crate) fn to_label_maybe_alpha(&self, alpha: bool) -> Label {
if alpha {
"_".into()
} else {
self.to_label()
}
}
pub(crate) fn to_label(&self) -> Label {
self.clone().into()
}
pub(crate) fn name(&self) -> &Label {
&self.name
}
}
/// Equality up to alpha-equivalence
impl std::cmp::PartialEq for AlphaVar {
fn eq(&self, other: &Self) -> bool {
self.alpha == other.alpha
}
}
/// Equality up to alpha-equivalence
impl std::cmp::PartialEq for Binder {
fn eq(&self, _other: &Self) -> bool {
true
}
}
impl std::fmt::Debug for AlphaVar {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "AlphaVar({})", self.alpha.1)
}
}
impl std::fmt::Debug for Binder {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "Binder({})", &self.name)
}
}
impl<'a> From<&'a Label> for AlphaVar {
fn from(x: &'a Label) -> AlphaVar {
AlphaVar { alpha: V((), 0) }
}
}
impl From<Binder> for AlphaVar {
fn from(x: Binder) -> AlphaVar {
AlphaVar { alpha: V((), 0) }
}
}
impl<'a> From<&'a Binder> for AlphaVar {
fn from(x: &'a Binder) -> AlphaVar {
x.clone().into()
}
}
impl From<Binder> for Label {
fn from(x: Binder) -> Label {
x.name
}
}
|
