Skip to main content

olean_export/
export.rs

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