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