Skip to main content

olean_export/env/
term.rs

1use serde::{Deserialize, Serialize};
2use std::{
3    fmt,
4    hash::{Hash, Hasher},
5    marker::PhantomData,
6};
7
8/// The id of a `T` in its table.
9#[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    /// The id as an index, for arrays sized by a table's `bound`.
18    #[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/// The universe levels of a constant, interned so that a `Const` node holds only an id.
45#[derive(Debug, Clone, PartialEq, Eq, Hash)]
46pub struct Univs(pub Box<[LevelId]>);
47
48pub type UnivsId = Id<Univs>;
49
50/// The fields of a `let`, boxed to keep `Expr` at 16 bytes.
51#[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/// Equality and hashing ignore binder names and annotations, matching Lean's `BEq Expr`,
84/// so terms that differ only there share one id, as they do in lean4export.
85#[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/// The value of an opaque constant.
195#[derive(Debug)]
196pub struct Body {
197    pub value: ExprId,
198    pub all: Vec<NameId>,
199}
200
201/// A theorem. Its value is `None` when [`Env::load_cone`] did not need it.
202#[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/// A declaration the kernel would accept. Unsafe and partial ones are dropped at load time.
251#[derive(Debug)]
252pub struct Const {
253    pub name: NameId,
254    pub level_params: Vec<NameId>,
255    pub ty: ExprId,
256    pub kind: Kind,
257}