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::{FxHashMap, 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    scope: Option<Box<Scope>>,
63}
64
65/// Per-module export: which modules declare each constant, what each module imports
66/// transitively, the module being written, and the entries its file took, to clear before
67/// the next. Lean realizes some constants, such as equation lemmas, in every module that
68/// needs them, and the environment keeps one copy, which may refer to private constants of
69/// a module the writer does not import. So a file holds what its module declares and
70/// whatever else it needs that no import provides.
71#[derive(Debug, Default)]
72struct Scope {
73    owner: FxHashMap<NameId, u32>,
74    more: FxHashMap<NameId, Vec<u32>>,
75    closure: Vec<Vec<u64>>,
76    module: u32,
77    names: Vec<NameId>,
78    levels: Vec<LevelId>,
79    exprs: Vec<ExprId>,
80    scanned: Vec<ExprId>,
81    visited: Vec<NameId>,
82}
83
84impl Scope {
85    fn new(env: &Env) -> Self {
86        let mut s = Self::default();
87        for m in 0..env.modules.len() {
88            let m32 = u32::try_from(m).expect("module count");
89            for &c in env.module_consts(m) {
90                if let Some(&o) = s.owner.get(&c) {
91                    if o != m32 {
92                        s.more.entry(c).or_default().push(m32);
93                    }
94                } else {
95                    s.owner.insert(c, m32);
96                }
97            }
98        }
99        let index: FxHashMap<&str, usize> = env
100            .modules
101            .iter()
102            .enumerate()
103            .map(|(i, m)| (m.as_str(), i))
104            .collect();
105        let words = env.modules.len().div_ceil(64);
106        for imports in &env.imports {
107            let mut bits = vec![0u64; words];
108            for &j in imports.iter().filter_map(|i| index.get(i.as_str())) {
109                if let Some(c) = s.closure.get(j) {
110                    bits.iter_mut().zip(c).for_each(|(b, c)| *b |= c);
111                    bits[j / 64] |= 1 << (j % 64);
112                }
113            }
114            s.closure.push(bits);
115        }
116        s
117    }
118
119    /// Whether the module being written writes `c`, rather than an import providing it.
120    fn writes(&self, c: NameId) -> bool {
121        let Some(&first) = self.owner.get(&c) else {
122            return true;
123        };
124        let owners = std::iter::once(first).chain(self.more.get(&c).into_iter().flatten().copied());
125        let mut provided = false;
126        for o in owners {
127            if o == self.module {
128                return true;
129            }
130            let bits = &self.closure[self.module as usize];
131            provided |= bits[o as usize / 64] >> (o % 64) & 1 == 1;
132        }
133        !provided
134    }
135}
136
137/// One step of [`Exporter::constant`]'s depth-first walk over dependencies.
138enum Task {
139    Const(NameId),
140    Scan(ExprId),
141    Scanned(ExprId),
142    Emit(NameId),
143}
144
145impl<'a, W: Write> Exporter<'a, Ndjson<W>> {
146    pub fn new(env: &'a Env, out: W) -> Self {
147        Self::with_sink(env, Ndjson::new(out))
148    }
149}
150
151impl<'a, S: Sink> Exporter<'a, S> {
152    pub fn with_sink(env: &'a Env, sink: S) -> Self {
153        Self::from_mark(env, sink, Mark::fresh(env))
154    }
155
156    /// Continue the export `mark` was taken from, on the same environment.
157    pub fn resume(env: &'a Env, sink: S, mark: Mark) -> Result<Self> {
158        if mark.lineage != env.lineage {
159            return Err(Error::Misuse("the mark is from another environment"));
160        }
161        Ok(Self::from_mark(env, sink, mark))
162    }
163
164    fn from_mark(env: &'a Env, sink: S, mut m: Mark) -> Self {
165        m.names.resize(env.names.bound(), UNSEEN);
166        m.levels.resize(env.levels.bound(), UNSEEN);
167        m.exprs.resize(env.exprs.bound(), UNSEEN);
168        m.scanned.resize(env.exprs.bound(), false);
169        Self {
170            env,
171            sink,
172            names: m.names,
173            levels: m.levels,
174            exprs: m.exprs,
175            next: m.next,
176            scanned: m.scanned,
177            visited: m.visited,
178            builtins: Builtins::find(env),
179            depth: Depth::Full,
180            scope: None,
181        }
182    }
183
184    /// An exporter that writes one module at a time with [`Exporter::module`], each to its
185    /// own sink after [`Exporter::split`]. A module's records refer to what its imports
186    /// declare by name only.
187    pub fn per_module(env: &'a Env, sink: S) -> Self {
188        let mut ex = Self::with_sink(env, sink);
189        ex.scope = Some(Box::new(Scope::new(env)));
190        ex
191    }
192
193    /// Write every constant module `m` declares. Internal ones are included, since a later
194    /// module may need them.
195    pub fn module(&mut self, m: usize) -> Result<()> {
196        let s = self
197            .scope
198            .as_mut()
199            .ok_or(Error::Misuse("module needs a per-module exporter"))?;
200        s.module = u32::try_from(m).expect("module count");
201        let env = self.env;
202        env.module_consts(m)
203            .iter()
204            .try_for_each(|&c| self.constant(c))
205    }
206
207    /// End the current file and start the next on `sink`, with ids from the start again.
208    /// Returns the finished sink's output.
209    pub fn split(&mut self, sink: S) -> Result<S::Output> {
210        let s = self
211            .scope
212            .as_mut()
213            .ok_or(Error::Misuse("split needs a per-module exporter"))?;
214        for n in s.names.drain(..) {
215            self.names[n.index()] = UNSEEN;
216        }
217        for l in s.levels.drain(..) {
218            self.levels[l.index()] = UNSEEN;
219        }
220        for e in s.exprs.drain(..) {
221            self.exprs[e.index()] = UNSEEN;
222        }
223        for e in s.scanned.drain(..) {
224            self.scanned[e.index()] = false;
225        }
226        for c in s.visited.drain(..) {
227            self.visited.remove(&c);
228        }
229        self.sink.record(None, &Record::End(self.next))?;
230        self.next = Counts::default();
231        std::mem::replace(&mut self.sink, sink).finish()
232    }
233
234    /// Write every theorem as an axiom over its type, so an environment from
235    /// [`Env::load_statements`] exports its statements and what they rest on, with no
236    /// proofs.
237    #[must_use]
238    pub const fn statements(mut self) -> Self {
239        self.depth = Depth::Statements;
240        self
241    }
242
243    pub fn meta(&mut self) -> Result<()> {
244        self.meta_with(None)
245    }
246
247    /// The `meta` record, with `module` added under that key when given.
248    pub fn meta_with(&mut self, module: Option<serde_json::Value>) -> Result<()> {
249        let h = &self.env.header;
250        let mut meta = serde_json::json!({
251            "exporter": {"name": "olean-export", "version": env!("CARGO_PKG_VERSION")},
252            "format": {"version": "3.1.0"},
253            "lean": {"githash": h.githash, "version": h.version},
254        });
255        if let Some(m) = module {
256            meta["module"] = m;
257        }
258        self.sink
259            .record(None, &Record::Meta(meta.to_string().into()))
260    }
261
262    /// Export every non-internal constant in load order, like `lean4export` with no `--`.
263    pub fn all(&mut self) -> Result<()> {
264        self.env.roots().try_for_each(|c| self.constant(c))
265    }
266
267    #[must_use]
268    pub const fn counts(&self) -> Counts {
269        self.next
270    }
271
272    /// Write the end record and hand back the sink's output.
273    pub fn finish(self) -> Result<S::Output> {
274        self.suspend().map(|(out, _)| out)
275    }
276
277    /// Like [`Exporter::finish`], with a [`Mark`] to [`Exporter::resume`] from.
278    pub fn suspend(mut self) -> Result<(S::Output, Mark)> {
279        self.sink.record(None, &Record::End(self.next))?;
280        let mark = Mark {
281            lineage: self.env.lineage,
282            names: self.names,
283            levels: self.levels,
284            exprs: self.exprs,
285            scanned: self.scanned,
286            visited: self.visited,
287            next: self.next,
288        };
289        Ok((self.sink.finish()?, mark))
290    }
291
292    /// After [`Env::reload`], export the reloaded constants again as [`Exporter::all`] would.
293    /// The end record counts every record since the first export.
294    /// An internal constant is written again if it was written before, since terms
295    /// already scanned will not lead back to it.
296    pub fn update(&mut self, r: &Reload) -> Result<()> {
297        for c in &r.removed {
298            self.visited.remove(c);
299        }
300        let env = self.env;
301        let again: Vec<NameId> = r
302            .consts
303            .iter()
304            .copied()
305            .filter(|c| self.visited.remove(c) | !env.is_internal(*c))
306            .collect();
307        again.into_iter().try_for_each(|c| self.constant(c))
308    }
309
310    fn name(&mut self, n: NameId) -> Result<u32> {
311        if self.names[n.index()] != UNSEEN {
312            return Ok(self.names[n.index()]);
313        }
314        let id = match &self.env.names[n] {
315            Name::Anon => unreachable!(),
316            Name::Str(p, s) => {
317                let p = self.name(*p)?;
318                self.emit(&Record::NameStr {
319                    pre: p,
320                    str: s.as_ref().into(),
321                })?
322            }
323            Name::Num(p, i) => {
324                let p = self.name(*p)?;
325                self.emit(&Record::NameNum { pre: p, i: *i })?
326            }
327        };
328        self.names[n.index()] = id;
329        if let Some(s) = &mut self.scope {
330            s.names.push(n);
331        }
332        Ok(id)
333    }
334
335    fn name_list(&mut self, ns: &[NameId]) -> Result<Vec<u32>> {
336        ns.iter().map(|&n| self.name(n)).collect()
337    }
338
339    fn level_params(&mut self, ps: &[NameId]) -> Result<Vec<u32>> {
340        let list = self.name_list(ps)?;
341        for &p in ps {
342            let l = self
343                .env
344                .levels
345                .get(&Level::Param(p))
346                .expect("level params are interned at load");
347            self.level(l)?;
348        }
349        Ok(list)
350    }
351
352    fn level(&mut self, l: LevelId) -> Result<u32> {
353        if self.levels[l.index()] != UNSEEN {
354            return Ok(self.levels[l.index()]);
355        }
356        let r = match self.env.levels[l] {
357            Level::Zero => unreachable!(),
358            Level::Succ(a) => Record::Succ(self.level(a)?),
359            Level::Max(a, b) => Record::Max(self.level(a)?, self.level(b)?),
360            Level::IMax(a, b) => Record::IMax(self.level(a)?, self.level(b)?),
361            Level::Param(n) => Record::Param(self.name(n)?),
362        };
363        let id = self.emit(&r)?;
364        self.levels[l.index()] = id;
365        if let Some(s) = &mut self.scope {
366            s.levels.push(l);
367        }
368        Ok(id)
369    }
370
371    /// Export `root` after its subterms. The worklist visits each term twice: first to
372    /// export the names and levels it mentions and queue its subterms, then to write it.
373    fn expr(&mut self, root: ExprId) -> Result<u32> {
374        let env = self.env;
375        let mut work = vec![(root, false)];
376        while let Some((e, ready)) = work.pop() {
377            if self.exprs[e.index()] != UNSEEN {
378                continue;
379            }
380            let x = &env.exprs[e];
381            if !ready {
382                work.push((e, true));
383                match x {
384                    Expr::BVar(_) => {}
385                    Expr::Sort(l) => {
386                        self.level(*l)?;
387                    }
388                    Expr::Const(n, us) => {
389                        self.name(*n)?;
390                        us.iter().try_for_each(|&u| self.level(u).map(drop))?;
391                    }
392                    Expr::App(f, a) => work.extend([(*a, false), (*f, false)]),
393                    Expr::Lam(n, t, b, _) | Expr::Pi(n, t, b, _) => {
394                        self.name(*n)?;
395                        work.extend([(*b, false), (*t, false)]);
396                    }
397                    Expr::Let(n, t, v, b) => {
398                        self.name(*n)?;
399                        work.extend([(*b, false), (*v, false), (*t, false)]);
400                    }
401                    Expr::Nat(_) | Expr::Str(_) => {
402                        let mut lits = Vec::new();
403                        self.env.children(e, &self.builtins, |d| lits.push(d));
404                        for d in lits {
405                            if let Dep::Literal(c) = d {
406                                self.constant(c)?;
407                            }
408                        }
409                    }
410                    Expr::Proj(n, _, x) => {
411                        self.name(*n)?;
412                        work.push((*x, false));
413                    }
414                }
415                continue;
416            }
417            let (names, levels, exprs) = (&self.names, &self.levels, &self.exprs);
418            let name = |n: &NameId| names[n.index()];
419            let level = |l: &LevelId| levels[l.index()];
420            let expr = |e: &ExprId| exprs[e.index()];
421            let bind = |n: &NameId, t: &ExprId, b: &ExprId, bi: &Binder| Binding {
422                info: *bi,
423                name: name(n),
424                ty: expr(t),
425                body: expr(b),
426            };
427            let r = match x {
428                Expr::BVar(i) => Record::BVar(*i),
429                Expr::Sort(l) => Record::Sort(level(l)),
430                Expr::Const(n, us) => Record::Const {
431                    name: name(n),
432                    us: us.iter().map(level).collect(),
433                },
434                Expr::App(f, a) => Record::App {
435                    fun: expr(f),
436                    arg: expr(a),
437                },
438                Expr::Lam(n, t, b, bi) => Record::Lam(bind(n, t, b, bi)),
439                Expr::Pi(n, t, b, bi) => Record::Pi(bind(n, t, b, bi)),
440                // Lean marks most `let`s nondep, but lean4export writes false for all of
441                // them so that terms differing only in the flag share one index.
442                Expr::Let(n, t, v, b) => Record::Let {
443                    name: name(n),
444                    ty: expr(t),
445                    value: expr(v),
446                    body: expr(b),
447                    nondep: false,
448                },
449                Expr::Nat(v) => Record::Nat(v.as_ref().into()),
450                Expr::Str(v) => Record::Str(v.as_ref().into()),
451                Expr::Proj(n, i, x) => Record::Proj {
452                    type_name: name(n),
453                    idx: *i,
454                    struct_: expr(x),
455                },
456            };
457            let id = self.emit(&r)?;
458            self.exprs[e.index()] = id;
459            if let Some(s) = &mut self.scope {
460                s.exprs.push(e);
461            }
462        }
463        Ok(self.exprs[root.index()])
464    }
465
466    /// Write a name, level or expression record and return its id.
467    fn emit(&mut self, r: &Record<'_>) -> Result<u32> {
468        let id = self.next.assign(r);
469        self.sink.record(id, r)?;
470        Ok(id.expect("emit takes only id-bearing records"))
471    }
472
473    fn decl(&mut self, d: Decl) -> Result<()> {
474        self.sink.record(None, &Record::Decl(d))
475    }
476
477    /// Export a constant and, first, everything it mentions. Dependencies are walked
478    /// depth-first on an explicit stack, so no term depth or dependency chain can overflow
479    /// the thread's stack.
480    pub fn constant(&mut self, c: NameId) -> Result<()> {
481        let env = self.env;
482        let mut work = vec![Task::Const(c)];
483        let mut members = Vec::new();
484        while let Some(task) = work.pop() {
485            match task {
486                Task::Scan(e) => {
487                    if !self.scanned[e.index()] {
488                        work.push(Task::Scanned(e));
489                        let at = work.len();
490                        env.children(e, &self.builtins, |d| match d {
491                            Dep::Expr(x) => work.push(Task::Scan(x)),
492                            Dep::Const(c) => work.push(Task::Const(c)),
493                            Dep::Member(_) | Dep::Literal(_) | Dep::Unloaded(_) => {}
494                        });
495                        work[at..].reverse();
496                    }
497                }
498                Task::Scanned(e) => {
499                    self.scanned[e.index()] = true;
500                    if let Some(s) = &mut self.scope {
501                        s.scanned.push(e);
502                    }
503                }
504                Task::Const(c) => {
505                    if self.scope.as_ref().is_some_and(|s| !s.writes(c)) {
506                        continue;
507                    }
508                    if !self.visit(c) {
509                        continue;
510                    }
511                    let Some(k) = env.consts.get(&c) else {
512                        continue;
513                    };
514                    if !matches!(k.kind, Kind::Ctor(_) | Kind::Rec(_)) {
515                        work.push(Task::Emit(c));
516                    }
517                    let at = work.len();
518                    let mut unloaded = None;
519                    env.mentions(k, self.depth, &self.builtins, |d| match d {
520                        Dep::Expr(e) => work.push(Task::Scan(e)),
521                        Dep::Const(c) => work.push(Task::Const(c)),
522                        Dep::Member(c) => members.push(c),
523                        Dep::Literal(_) => {}
524                        Dep::Unloaded(c) => unloaded = Some(c),
525                    })?;
526                    if let Some(c) = unloaded {
527                        return Err(corrupt(format!(
528                            "the value of {} was not loaded",
529                            env.display(c)
530                        )));
531                    }
532                    work[at..].reverse();
533                    for c in std::mem::take(&mut members) {
534                        self.visit(c);
535                    }
536                }
537                Task::Emit(c) => self.write(c)?,
538            }
539        }
540        Ok(())
541    }
542
543    fn visit(&mut self, c: NameId) -> bool {
544        let new = self.visited.insert(c);
545        if let Some(s) = self.scope.as_mut().filter(|_| new) {
546            s.visited.push(c);
547        }
548        new
549    }
550
551    /// Write the declaration of `c`, whose dependencies are already out.
552    fn write(&mut self, c: NameId) -> Result<()> {
553        let k = &self.env.consts[&c];
554        match &k.kind {
555            Kind::Thm(_) if self.depth == Depth::Statements => {
556                let head = self.header(k)?;
557                self.decl(Decl::Axiom {
558                    head,
559                    is_unsafe: false,
560                    all: None,
561                })
562            }
563            Kind::Axiom => {
564                let head = self.header(k)?;
565                self.decl(Decl::Axiom {
566                    head,
567                    is_unsafe: false,
568                    all: None,
569                })
570            }
571            Kind::Defn(d) => {
572                let head = self.header(k)?;
573                let value = self.expr(d.value)?;
574                let all = self.name_list(&d.all)?;
575                self.decl(Decl::Def {
576                    head,
577                    value,
578                    hints: d.hints,
579                    all,
580                    safety: Safety::Safe,
581                })
582            }
583            Kind::Thm(t) => {
584                let head = self.header(k)?;
585                let value = self.expr(t.value.expect("scanned"))?;
586                let all = self.name_list(&t.all)?;
587                self.decl(Decl::Thm { head, value, all })
588            }
589            Kind::Opaque(b) => {
590                let head = self.header(k)?;
591                let value = self.expr(b.value)?;
592                let all = self.name_list(&b.all)?;
593                self.decl(Decl::Opaque {
594                    head,
595                    value,
596                    is_unsafe: false,
597                    all: Some(all),
598                })
599            }
600            Kind::Quot(_) => self.quot(),
601            Kind::Induct(ind) => self.inductive(k, ind),
602            Kind::Ctor(_) | Kind::Rec(_) => unreachable!("exported through their inductive"),
603        }
604    }
605
606    fn header(&mut self, k: &Const) -> Result<Head> {
607        Ok(Head {
608            name: self.name(k.name)?,
609            level_params: self.level_params(&k.level_params)?,
610            ty: self.expr(k.ty)?,
611        })
612    }
613
614    fn quot(&mut self) -> Result<()> {
615        let env = self.env;
616        let [_, rest @ ..] = self.builtins.quot;
617        for c in rest.into_iter().flatten() {
618            let (k, &kind) = env.lookup(c, "quotient", |k| match k {
619                Kind::Quot(q) => Some(q),
620                _ => None,
621            })?;
622            let head = self.header(k)?;
623            self.decl(Decl::Quot { head, kind })?;
624        }
625        Ok(())
626    }
627
628    fn inductive(&mut self, base: &Const, ind: &Inductive) -> Result<()> {
629        let Family { types, ctors, recs } = self.env.family(base, ind)?;
630        let mut out_ctors = Vec::with_capacity(ctors.len());
631        for &(c, ctor) in &ctors {
632            let Ctor {
633                induct,
634                cidx,
635                num_params,
636                num_fields,
637            } = *ctor;
638            let head = self.header(c)?;
639            out_ctors.push(IndCtor {
640                head,
641                is_unsafe: false,
642                induct: self.name(induct)?,
643                cidx,
644                num_params,
645                num_fields,
646            });
647        }
648        let mut out_recs = Vec::with_capacity(recs.len());
649        for &(r, rec) in &recs {
650            let Rec {
651                all,
652                num_params,
653                num_indices,
654                num_motives,
655                num_minors,
656                rules,
657                k,
658            } = rec;
659            let head = self.header(r)?;
660            let all = self.name_list(all)?;
661            let rules = rules
662                .iter()
663                .map(|rule| {
664                    Ok(IndRule {
665                        ctor: self.name(rule.ctor)?,
666                        nfields: rule.nfields,
667                        rhs: self.expr(rule.rhs)?,
668                    })
669                })
670                .collect::<Result<Vec<_>>>()?;
671            out_recs.push(IndRec {
672                head,
673                is_unsafe: false,
674                all,
675                num_params: *num_params,
676                num_indices: *num_indices,
677                num_motives: *num_motives,
678                num_minors: *num_minors,
679                rules,
680                k: *k,
681            });
682        }
683        let mut out_types = Vec::with_capacity(types.len());
684        for &(ty, ind) in &types {
685            let Inductive {
686                num_params,
687                num_indices,
688                all,
689                ctors,
690                num_nested,
691                is_rec,
692                is_reflexive,
693            } = ind;
694            let head = self.header(ty)?;
695            let (all, ctors) = (self.name_list(all)?, self.name_list(ctors)?);
696            out_types.push(IndType {
697                head,
698                is_unsafe: false,
699                num_params: *num_params,
700                num_indices: *num_indices,
701                all,
702                ctors,
703                num_nested: *num_nested,
704                is_rec: *is_rec,
705                is_reflexive: *is_reflexive,
706            });
707        }
708        self.decl(Decl::Inductive {
709            types: out_types,
710            ctors: out_ctors,
711            recs: out_recs,
712        })
713    }
714}