1use serde::{Deserialize, Serialize};
2use std::{
3 fmt,
4 hash::{Hash, Hasher},
5 marker::PhantomData,
6};
7
8#[derive(PartialEq, Eq, Hash)]
10pub struct Id<T>(pub(super) u32, PhantomData<fn() -> T>);
11
12impl<T> Id<T> {
13 pub(super) const fn new(i: u32) -> Self {
14 Self(i, PhantomData)
15 }
16
17 #[must_use]
19 pub const fn index(self) -> usize {
20 self.0 as usize
21 }
22}
23
24impl<T> Clone for Id<T> {
25 fn clone(&self) -> Self {
26 *self
27 }
28}
29
30impl<T> Copy for Id<T> {}
31
32impl<T> fmt::Debug for Id<T> {
33 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
34 write!(f, "#{}", self.0)
35 }
36}
37
38pub type NameId = Id<Name>;
39
40pub type LevelId = Id<Level>;
41
42pub type ExprId = Id<Expr>;
43
44#[derive(Debug, Clone, PartialEq, Eq, Hash)]
46pub struct Univs(pub Box<[LevelId]>);
47
48pub type UnivsId = Id<Univs>;
49
50#[derive(Debug, Clone)]
52pub struct LetNode(pub NameId, pub ExprId, pub ExprId, pub ExprId);
53
54pub const ANON: NameId = Id::new(0);
55
56pub const ZERO: LevelId = Id::new(0);
57
58#[derive(Debug, Clone, PartialEq, Eq, Hash)]
59pub enum Name {
60 Anon,
61 Str(NameId, Box<str>),
62 Num(NameId, u64),
63}
64
65#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
66pub enum Level {
67 Zero,
68 Succ(LevelId),
69 Max(LevelId, LevelId),
70 IMax(LevelId, LevelId),
71 Param(NameId),
72}
73
74#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
75#[serde(rename_all = "camelCase")]
76pub enum Binder {
77 Default,
78 Implicit,
79 StrictImplicit,
80 InstImplicit,
81}
82
83#[derive(Debug, Clone)]
86pub enum Expr {
87 BVar(u64),
88 Sort(LevelId),
89 Const(NameId, UnivsId),
90 App(ExprId, ExprId),
91 Lam(NameId, ExprId, ExprId, Binder),
92 Pi(NameId, ExprId, ExprId, Binder),
93 Let(Box<LetNode>),
94 Nat(Box<Box<str>>),
95 Str(Box<Box<str>>),
96 Proj(NameId, u32, ExprId),
97}
98
99const _: () = assert!(std::mem::size_of::<Expr>() == 16);
100
101impl PartialEq for Expr {
102 fn eq(&self, other: &Self) -> bool {
103 match (self, other) {
104 (Self::BVar(a), Self::BVar(b)) => a == b,
105 (Self::Sort(a), Self::Sort(b)) => a == b,
106 (Self::Const(n, us), Self::Const(m, vs)) => n == m && us == vs,
107 (Self::App(f, a), Self::App(g, b)) => f == g && a == b,
108 (Self::Lam(_, t, b, _), Self::Lam(_, u, c, _))
109 | (Self::Pi(_, t, b, _), Self::Pi(_, u, c, _)) => t == u && b == c,
110 (Self::Let(x), Self::Let(y)) => x.1 == y.1 && x.2 == y.2 && x.3 == y.3,
111 (Self::Nat(a), Self::Nat(b)) | (Self::Str(a), Self::Str(b)) => a == b,
112 (Self::Proj(n, i, x), Self::Proj(m, j, y)) => n == m && i == j && x == y,
113 _ => false,
114 }
115 }
116}
117
118impl Eq for Expr {}
119
120impl Hash for Expr {
121 fn hash<H: Hasher>(&self, h: &mut H) {
122 let pack = |a: u32, b: u32| u64::from(a) << 32 | u64::from(b);
123 match self {
124 Self::BVar(i) => h.write_u64(*i),
125 Self::Sort(l) => h.write_u32(l.0),
126 Self::Const(n, us) => {
127 h.write_u32(n.0);
128 h.write_u32(us.0);
129 }
130 Self::App(f, a) => h.write_u64(pack(f.0, a.0)),
131 Self::Lam(_, t, b, _) | Self::Pi(_, t, b, _) => h.write_u64(pack(t.0, b.0)),
132 Self::Let(l) => {
133 h.write_u64(pack(l.1 .0, l.2 .0));
134 h.write_u32(l.3 .0);
135 }
136 Self::Nat(v) | Self::Str(v) => h.write(v.as_bytes()),
137 Self::Proj(n, i, x) => {
138 h.write_u64(pack(n.0, x.0));
139 h.write_u64(u64::from(*i));
140 }
141 }
142 h.write_u8(self.tag());
143 }
144}
145
146impl Expr {
147 const fn tag(&self) -> u8 {
148 match self {
149 Self::BVar(_) => 0,
150 Self::Sort(_) => 1,
151 Self::Const(..) => 2,
152 Self::App(..) => 3,
153 Self::Lam(..) => 4,
154 Self::Pi(..) => 5,
155 Self::Let(..) => 6,
156 Self::Nat(_) => 7,
157 Self::Str(_) => 8,
158 Self::Proj(..) => 9,
159 }
160 }
161}
162
163#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
164#[serde(rename_all = "lowercase")]
165pub enum Hints {
166 Opaque,
167 Abbrev,
168 Regular(u32),
169}
170
171#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
172#[serde(rename_all = "lowercase")]
173pub enum QuotKind {
174 Type,
175 Ctor,
176 Lift,
177 Ind,
178}
179
180#[derive(Debug)]
181pub struct Rule {
182 pub ctor: NameId,
183 pub nfields: u64,
184 pub rhs: ExprId,
185}
186
187#[derive(Debug)]
188pub struct Defn {
189 pub value: ExprId,
190 pub hints: Hints,
191 pub all: Vec<NameId>,
192}
193
194#[derive(Debug)]
196pub struct Body {
197 pub value: ExprId,
198 pub all: Vec<NameId>,
199}
200
201#[derive(Debug)]
203pub struct Theorem {
204 pub value: Option<ExprId>,
205 pub all: Vec<NameId>,
206}
207
208#[derive(Debug)]
209pub struct Inductive {
210 pub num_params: u64,
211 pub num_indices: u64,
212 pub all: Vec<NameId>,
213 pub ctors: Vec<NameId>,
214 pub num_nested: u64,
215 pub is_rec: bool,
216 pub is_reflexive: bool,
217}
218
219#[derive(Debug)]
220pub struct Ctor {
221 pub induct: NameId,
222 pub cidx: u64,
223 pub num_params: u64,
224 pub num_fields: u64,
225}
226
227#[derive(Debug)]
228pub struct Rec {
229 pub all: Vec<NameId>,
230 pub num_params: u64,
231 pub num_indices: u64,
232 pub num_motives: u64,
233 pub num_minors: u64,
234 pub rules: Vec<Rule>,
235 pub k: bool,
236}
237
238#[derive(Debug)]
239pub enum Kind {
240 Axiom,
241 Defn(Defn),
242 Thm(Theorem),
243 Opaque(Body),
244 Quot(QuotKind),
245 Induct(Inductive),
246 Ctor(Ctor),
247 Rec(Rec),
248}
249
250#[derive(Debug)]
252pub struct Const {
253 pub name: NameId,
254 pub level_params: Vec<NameId>,
255 pub ty: ExprId,
256 pub kind: Kind,
257}