Skip to main content

olean_export/
export.rs

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