Skip to main content

olean_export/
export.rs

1use crate::{
2    env::{
3        Const, Ctor, Env, Expr, ExprId, Inductive, Kind, Level, LevelId, Name, NameId, Rec, ANON,
4        ZERO,
5    },
6    error::{corrupt, Result},
7    ndjson::Ndjson,
8    record::{
9        Binding, Counts, Decl, Head, IndCtor, IndRec, IndRule, IndType, Record, Safety, Sink,
10    },
11};
12use rustc_hash::FxHashSet;
13use std::io::Write;
14
15const UNSEEN: u32 = u32::MAX;
16
17/// Streams an [`Env`] in lean4export 3.1.0 order to a [`Sink`], NDJSON by default. Ids are
18/// assigned on first use and every record only refers to records already written.
19///
20/// Exporting recurses once per nested subterm, which overflows the default stack on large
21/// libraries such as Mathlib, so run it inside [`crate::with_big_stack`].
22#[derive(Debug)]
23pub struct Exporter<'a, S: Sink> {
24    env: &'a Env,
25    sink: S,
26    names: Vec<u32>,
27    levels: Vec<u32>,
28    exprs: Vec<u32>,
29    next: Counts,
30    scanned: Vec<bool>,
31    visited: FxHashSet<NameId>,
32    nat: Option<NameId>,
33    str_deps: [Option<NameId>; 2],
34    quot: [Option<NameId>; 5],
35}
36
37impl<'a, W: Write> Exporter<'a, Ndjson<W>> {
38    pub fn new(env: &'a Env, out: W) -> Self {
39        Self::with_sink(env, Ndjson::new(out))
40    }
41}
42
43impl<'a, S: Sink> Exporter<'a, S> {
44    pub fn with_sink(env: &'a Env, sink: S) -> Self {
45        let mut names = vec![UNSEEN; env.names.bound()];
46        let mut levels = vec![UNSEEN; env.levels.bound()];
47        names[ANON.index()] = 0;
48        levels[ZERO.index()] = 0;
49        let find = |s| env.find_name(s);
50        Self {
51            env,
52            sink,
53            names,
54            levels,
55            exprs: vec![UNSEEN; env.exprs.bound()],
56            next: Counts::default(),
57            scanned: vec![false; env.exprs.bound()],
58            visited: FxHashSet::default(),
59            nat: find("Nat"),
60            str_deps: [find("Char.ofNat"), find("String.ofList")],
61            quot: [
62                find("Eq"),
63                find("Quot"),
64                find("Quot.mk"),
65                find("Quot.lift"),
66                find("Quot.ind"),
67            ],
68        }
69    }
70
71    pub fn meta(&mut self) -> Result<()> {
72        let h = &self.env.header;
73        let meta = format!(
74            r#"{{"exporter":{{"name":"olean-export","version":"{}"}},"format":{{"version":"3.1.0"}},"lean":{{"githash":"{}","version":"{}"}}}}"#,
75            env!("CARGO_PKG_VERSION"),
76            h.githash,
77            h.version
78        );
79        self.sink.record(&Record::Meta(meta.into()))
80    }
81
82    /// Export every non-internal constant in load order, like `lean4export` with no `--`.
83    pub fn all(&mut self) -> Result<()> {
84        self.env.roots().try_for_each(|c| self.constant(c))
85    }
86
87    #[must_use]
88    pub const fn counts(&self) -> Counts {
89        self.next
90    }
91
92    /// Write the end record and hand back the sink's output.
93    pub fn finish(mut self) -> Result<S::Output> {
94        self.sink.record(&Record::End(self.next))?;
95        self.sink.finish()
96    }
97
98    fn name(&mut self, n: NameId) -> Result<u32> {
99        if self.names[n.index()] != UNSEEN {
100            return Ok(self.names[n.index()]);
101        }
102        let id = match &self.env.names[n] {
103            Name::Anon => unreachable!(),
104            Name::Str(p, s) => {
105                let p = self.name(*p)?;
106                self.emit(&Record::NameStr {
107                    pre: p,
108                    str: s.as_ref().into(),
109                })?
110            }
111            Name::Num(p, i) => {
112                let p = self.name(*p)?;
113                self.emit(&Record::NameNum { pre: p, i: *i })?
114            }
115        };
116        self.names[n.index()] = id;
117        Ok(id)
118    }
119
120    fn name_list(&mut self, ns: &[NameId]) -> Result<Vec<u32>> {
121        ns.iter().map(|&n| self.name(n)).collect()
122    }
123
124    fn level_params(&mut self, ps: &[NameId]) -> Result<Vec<u32>> {
125        let list = self.name_list(ps)?;
126        for &p in ps {
127            let l = self
128                .env
129                .levels
130                .get(&Level::Param(p))
131                .expect("level params are interned at load");
132            self.level(l)?;
133        }
134        Ok(list)
135    }
136
137    fn level(&mut self, l: LevelId) -> Result<u32> {
138        if self.levels[l.index()] != UNSEEN {
139            return Ok(self.levels[l.index()]);
140        }
141        let r = match self.env.levels[l] {
142            Level::Zero => unreachable!(),
143            Level::Succ(a) => Record::Succ(self.level(a)?),
144            Level::Max(a, b) => Record::Max(self.level(a)?, self.level(b)?),
145            Level::IMax(a, b) => Record::IMax(self.level(a)?, self.level(b)?),
146            Level::Param(n) => Record::Param(self.name(n)?),
147        };
148        let id = self.emit(&r)?;
149        self.levels[l.index()] = id;
150        Ok(id)
151    }
152
153    fn expr(&mut self, e: ExprId) -> Result<u32> {
154        if self.exprs[e.index()] != UNSEEN {
155            return Ok(self.exprs[e.index()]);
156        }
157        let env = self.env;
158        let r = match &env.exprs[e] {
159            Expr::BVar(i) => Record::BVar(*i),
160            Expr::Sort(l) => Record::Sort(self.level(*l)?),
161            Expr::Const(n, us) => Record::Const {
162                name: self.name(*n)?,
163                us: us.iter().map(|&u| self.level(u)).collect::<Result<_>>()?,
164            },
165            Expr::App(f, a) => Record::App {
166                fun: self.expr(*f)?,
167                arg: self.expr(*a)?,
168            },
169            Expr::Lam(n, t, b, bi) => Record::Lam(self.binding(*n, *t, *b, *bi)?),
170            Expr::Pi(n, t, b, bi) => Record::Pi(self.binding(*n, *t, *b, *bi)?),
171            Expr::Let(n, t, v, b) => {
172                let (n, t, v, b) = (
173                    self.name(*n)?,
174                    self.expr(*t)?,
175                    self.expr(*v)?,
176                    self.expr(*b)?,
177                );
178                // Lean marks most `let`s nondep, but lean4export writes false for all of
179                // them so that terms differing only in the flag share one index.
180                Record::Let {
181                    name: n,
182                    ty: t,
183                    value: v,
184                    body: b,
185                    nondep: false,
186                }
187            }
188            Expr::Nat(v) => {
189                if let Some(nat) = self.nat {
190                    self.constant(nat)?;
191                }
192                Record::Nat(v.as_ref().into())
193            }
194            Expr::Str(v) => {
195                for c in self.str_deps.into_iter().flatten() {
196                    self.constant(c)?;
197                }
198                Record::Str(v.as_ref().into())
199            }
200            Expr::Proj(n, i, x) => {
201                let (n, x) = (self.name(*n)?, self.expr(*x)?);
202                Record::Proj {
203                    type_name: n,
204                    idx: *i,
205                    struct_: x,
206                }
207            }
208        };
209        let id = self.emit(&r)?;
210        self.exprs[e.index()] = id;
211        Ok(id)
212    }
213
214    fn binding(
215        &mut self,
216        n: NameId,
217        t: ExprId,
218        b: ExprId,
219        info: crate::env::Binder,
220    ) -> Result<Binding> {
221        Ok(Binding {
222            info,
223            name: self.name(n)?,
224            ty: self.expr(t)?,
225            body: self.expr(b)?,
226        })
227    }
228
229    /// Write a name, level or expression record and return its id.
230    fn emit(&mut self, r: &Record<'_>) -> Result<u32> {
231        self.sink.record(r)?;
232        Ok(self
233            .next
234            .assign(r)
235            .expect("emit takes only id-bearing records"))
236    }
237
238    fn decl(&mut self, d: Decl) -> Result<()> {
239        self.sink.record(&Record::Decl(d))
240    }
241
242    fn deps(&mut self, e: ExprId) -> Result<()> {
243        if self.scanned[e.index()] {
244            return Ok(());
245        }
246        match &self.env.exprs[e] {
247            Expr::Const(n, _) => self.constant(*n)?,
248            Expr::App(a, b) | Expr::Lam(_, a, b, _) | Expr::Pi(_, a, b, _) => {
249                self.deps(*a)?;
250                self.deps(*b)?;
251            }
252            Expr::Let(_, t, v, b) => {
253                self.deps(*t)?;
254                self.deps(*v)?;
255                self.deps(*b)?;
256            }
257            Expr::Proj(_, _, x) => self.deps(*x)?,
258            Expr::BVar(_) | Expr::Sort(_) | Expr::Nat(_) | Expr::Str(_) => {}
259        }
260        self.scanned[e.index()] = true;
261        Ok(())
262    }
263
264    /// Export a constant and, first, everything it mentions.
265    pub fn constant(&mut self, c: NameId) -> Result<()> {
266        if !self.visited.insert(c) {
267            return Ok(());
268        }
269        let env = self.env;
270        let Some(k) = env.consts.get(&c) else {
271            return Ok(());
272        };
273        match &k.kind {
274            Kind::Axiom => {
275                self.deps(k.ty)?;
276                let head = self.header(k)?;
277                self.decl(Decl::Axiom {
278                    head,
279                    is_unsafe: false,
280                    all: None,
281                })
282            }
283            Kind::Defn(d) => {
284                self.deps(k.ty)?;
285                self.deps(d.value)?;
286                let head = self.header(k)?;
287                let value = self.expr(d.value)?;
288                let all = self.name_list(&d.all)?;
289                self.decl(Decl::Def {
290                    head,
291                    value,
292                    hints: d.hints,
293                    all,
294                    safety: Safety::Safe,
295                })
296            }
297            Kind::Thm(b) | Kind::Opaque(b) => {
298                self.deps(k.ty)?;
299                self.deps(b.value)?;
300                let head = self.header(k)?;
301                let value = self.expr(b.value)?;
302                let all = self.name_list(&b.all)?;
303                self.decl(if matches!(k.kind, Kind::Thm(_)) {
304                    Decl::Thm { head, value, all }
305                } else {
306                    Decl::Opaque {
307                        head,
308                        value,
309                        is_unsafe: false,
310                        all: Some(all),
311                    }
312                })
313            }
314            Kind::Quot(_) => self.quot(),
315            Kind::Induct(ind) => self.inductive(k, ind),
316            Kind::Ctor(ctor) => self.constant(ctor.induct),
317            Kind::Rec(rec) => rec.all.iter().try_for_each(|&i| self.constant(i)),
318        }
319    }
320
321    fn header(&mut self, k: &Const) -> Result<Head> {
322        Ok(Head {
323            name: self.name(k.name)?,
324            level_params: self.level_params(&k.level_params)?,
325            ty: self.expr(k.ty)?,
326        })
327    }
328
329    fn quot(&mut self) -> Result<()> {
330        let env = self.env;
331        let [eq, rest @ ..] = self.quot;
332        if let Some(eq) = eq {
333            self.constant(eq)?;
334        }
335        for c in rest.into_iter().flatten() {
336            self.visited.insert(c);
337            let (k, &kind) = lookup(env, c, "quotient", |k| match k {
338                Kind::Quot(q) => Some(q),
339                _ => None,
340            })?;
341            let head = self.header(k)?;
342            self.decl(Decl::Quot { head, kind })?;
343        }
344        Ok(())
345    }
346
347    fn inductive(&mut self, base: &Const, ind: &Inductive) -> Result<()> {
348        let env = self.env;
349        let types = ind
350            .all
351            .iter()
352            .map(|&n| {
353                lookup(env, n, "inductive", |k| match k {
354                    Kind::Induct(i) => Some(i),
355                    _ => None,
356                })
357            })
358            .collect::<Result<Vec<_>>>()?;
359        let mut ctors = Vec::new();
360        for &(t, i) in &types {
361            for &c in &i.ctors {
362                ctors.push(lookup(env, c, "constructor", |k| match k {
363                    Kind::Ctor(c) => Some(c),
364                    _ => None,
365                })?);
366            }
367            self.visited.insert(t.name);
368            self.deps(t.ty)?;
369        }
370        for &(c, _) in &ctors {
371            self.visited.insert(c.name);
372            self.deps(c.ty)?;
373        }
374        let recs = env
375            .recursors
376            .get(&base.name)
377            .map_or(&[][..], Vec::as_slice)
378            .iter()
379            .map(|&r| {
380                lookup(env, r, "recursor", |k| match k {
381                    Kind::Rec(r) => Some(r),
382                    _ => None,
383                })
384            })
385            .collect::<Result<Vec<_>>>()?;
386        for &(r, _) in &recs {
387            self.visited.insert(r.name);
388            self.deps(r.ty)?;
389        }
390        for (_, rec) in &recs {
391            for rule in &rec.rules {
392                self.deps(rule.rhs)?;
393            }
394        }
395        let mut out_ctors = Vec::with_capacity(ctors.len());
396        for &(c, ctor) in &ctors {
397            let Ctor {
398                induct,
399                cidx,
400                num_params,
401                num_fields,
402            } = *ctor;
403            let head = self.header(c)?;
404            out_ctors.push(IndCtor {
405                head,
406                is_unsafe: false,
407                induct: self.name(induct)?,
408                cidx,
409                num_params,
410                num_fields,
411            });
412        }
413        let mut out_recs = Vec::with_capacity(recs.len());
414        for &(r, rec) in &recs {
415            let Rec {
416                all,
417                num_params,
418                num_indices,
419                num_motives,
420                num_minors,
421                rules,
422                k,
423            } = rec;
424            let head = self.header(r)?;
425            let all = self.name_list(all)?;
426            let rules = rules
427                .iter()
428                .map(|rule| {
429                    Ok(IndRule {
430                        ctor: self.name(rule.ctor)?,
431                        nfields: rule.nfields,
432                        rhs: self.expr(rule.rhs)?,
433                    })
434                })
435                .collect::<Result<Vec<_>>>()?;
436            out_recs.push(IndRec {
437                head,
438                is_unsafe: false,
439                all,
440                num_params: *num_params,
441                num_indices: *num_indices,
442                num_motives: *num_motives,
443                num_minors: *num_minors,
444                rules,
445                k: *k,
446            });
447        }
448        let mut out_types = Vec::with_capacity(types.len());
449        for &(ty, ind) in &types {
450            let Inductive {
451                num_params,
452                num_indices,
453                all,
454                ctors,
455                num_nested,
456                is_rec,
457                is_reflexive,
458            } = ind;
459            let head = self.header(ty)?;
460            let (all, ctors) = (self.name_list(all)?, self.name_list(ctors)?);
461            out_types.push(IndType {
462                head,
463                is_unsafe: false,
464                num_params: *num_params,
465                num_indices: *num_indices,
466                all,
467                ctors,
468                num_nested: *num_nested,
469                is_rec: *is_rec,
470                is_reflexive: *is_reflexive,
471            });
472        }
473        self.decl(Decl::Inductive {
474            types: out_types,
475            ctors: out_ctors,
476            recs: out_recs,
477        })
478    }
479}
480
481/// The constant `n` and the part of its kind that `pick` selects, or an error saying it is
482/// not the `what` the referring constant claims.
483fn lookup<'e, T>(
484    env: &'e Env,
485    n: NameId,
486    what: &str,
487    pick: impl Fn(&'e Kind) -> Option<&'e T>,
488) -> Result<(&'e Const, &'e T)> {
489    env.consts
490        .get(&n)
491        .and_then(|c| Some((c, pick(&c.kind)?)))
492        .ok_or_else(|| corrupt(format!("{} is not a known {what}", env.display(n))))
493}