Skip to main content

olean_export/
export.rs

1use crate::{
2    env::{
3        Binder, Const, Ctor, Env, Expr, ExprId, Hints, Inductive, Kind, Level, LevelId, Name,
4        NameId, QuotKind, Rec, ANON, ZERO,
5    },
6    error::{corrupt, Result},
7};
8use rustc_hash::FxHashSet;
9use std::{fmt::Write as _, io::Write};
10
11const UNSEEN: u32 = u32::MAX;
12
13/// Lines written so far for each table, which is also the next id each hands out.
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub struct Counts {
16    pub names: u32,
17    pub levels: u32,
18    pub exprs: u32,
19}
20
21/// Streams an [`Env`] in the lean4export 3.1.0 NDJSON format. Ids are assigned on first
22/// use and every line only refers to lines already written.
23///
24/// Exporting recurses once per nested subterm, which overflows the default stack on large
25/// libraries such as Mathlib, so run it inside [`crate::with_big_stack`].
26#[derive(Debug)]
27pub struct Exporter<'a, W: Write> {
28    env: &'a Env,
29    out: W,
30    names: Vec<u32>,
31    levels: Vec<u32>,
32    exprs: Vec<u32>,
33    next: Counts,
34    scanned: Vec<bool>,
35    visited: FxHashSet<NameId>,
36    nat: Option<NameId>,
37    str_deps: [Option<NameId>; 2],
38    quot: [Option<NameId>; 5],
39    buf: Line,
40}
41
42/// A reusable output line, since `format!` per record dominated export time.
43#[derive(Debug, Default)]
44struct Line(Vec<u8>);
45
46impl Line {
47    fn s(&mut self, s: &str) -> &mut Self {
48        self.0.extend_from_slice(s.as_bytes());
49        self
50    }
51
52    fn n(&mut self, n: impl itoa::Integer) -> &mut Self {
53        self.s(itoa::Buffer::new().format(n))
54    }
55
56    fn list(&mut self, ids: &[u32]) -> &mut Self {
57        self.s("[");
58        for (i, &id) in ids.iter().enumerate() {
59            if i > 0 {
60                self.s(",");
61            }
62            self.n(id);
63        }
64        self.s("]")
65    }
66
67    fn q(&mut self, s: &str) -> &mut Self {
68        self.s("\"");
69        for c in s.chars() {
70            match c {
71                '"' => self.s("\\\""),
72                '\\' => self.s("\\\\"),
73                '\n' => self.s("\\n"),
74                '\r' => self.s("\\r"),
75                '\t' => self.s("\\t"),
76                c if (c as u32) < 0x20 || c == '\u{7f}' => {
77                    self.s("\\u00").s(&format!("{:02x}", c as u32))
78                }
79                c => self.s(c.encode_utf8(&mut [0; 4])),
80            };
81        }
82        self.s("\"")
83    }
84}
85
86impl<'a, W: Write> Exporter<'a, W> {
87    pub fn new(env: &'a Env, out: W) -> Self {
88        let mut names = vec![UNSEEN; env.names.bound()];
89        let mut levels = vec![UNSEEN; env.levels.bound()];
90        names[ANON.index()] = 0;
91        levels[ZERO.index()] = 0;
92        let find = |s| env.find_name(s);
93        Self {
94            env,
95            out,
96            names,
97            levels,
98            exprs: vec![UNSEEN; env.exprs.bound()],
99            next: Counts {
100                names: 1,
101                levels: 1,
102                exprs: 0,
103            },
104            scanned: vec![false; env.exprs.bound()],
105            visited: FxHashSet::default(),
106            nat: find("Nat"),
107            str_deps: [find("Char.ofNat"), find("String.ofList")],
108            quot: [
109                find("Eq"),
110                find("Quot"),
111                find("Quot.mk"),
112                find("Quot.lift"),
113                find("Quot.ind"),
114            ],
115            buf: Line::default(),
116        }
117    }
118
119    pub fn meta(&mut self) -> Result<()> {
120        let h = &self.env.header;
121        writeln!(
122            self.out,
123            r#"{{"meta":{{"exporter":{{"name":"olean-export","version":"{}"}},"format":{{"version":"3.1.0"}},"lean":{{"githash":"{}","version":"{}"}}}}}}"#,
124            env!("CARGO_PKG_VERSION"),
125            h.githash,
126            h.version
127        )?;
128        Ok(())
129    }
130
131    /// Export every non-internal constant in load order, like `lean4export` with no `--`.
132    pub fn all(&mut self) -> Result<()> {
133        self.env.roots().try_for_each(|c| self.constant(c))
134    }
135
136    #[must_use]
137    pub const fn counts(&self) -> Counts {
138        self.next
139    }
140
141    pub fn finish(mut self) -> Result<W> {
142        self.out.flush()?;
143        Ok(self.out)
144    }
145
146    fn start(&mut self) -> &mut Line {
147        self.buf.0.clear();
148        &mut self.buf
149    }
150
151    fn emit(&mut self) -> Result<()> {
152        self.buf.0.push(b'\n');
153        self.out.write_all(&self.buf.0)?;
154        Ok(())
155    }
156
157    fn line(&mut self, s: &str) -> Result<()> {
158        self.out.write_all(s.as_bytes())?;
159        self.out.write_all(b"\n")?;
160        Ok(())
161    }
162
163    fn name(&mut self, n: NameId) -> Result<u32> {
164        if self.names[n.index()] != UNSEEN {
165            return Ok(self.names[n.index()]);
166        }
167        let id = match &self.env.names[n] {
168            Name::Anon => unreachable!(),
169            Name::Str(p, s) => {
170                let p = self.name(*p)?;
171                let id = fresh(&mut self.next.names);
172                self.start()
173                    .s(r#"{"in":"#)
174                    .n(id)
175                    .s(r#","str":{"pre":"#)
176                    .n(p);
177                self.buf.s(r#","str":"#).q(s).s("}}");
178                id
179            }
180            Name::Num(p, i) => {
181                let p = self.name(*p)?;
182                let id = fresh(&mut self.next.names);
183                self.start().s(r#"{"in":"#).n(id).s(r#","num":{"i":"#).n(*i);
184                self.buf.s(r#","pre":"#).n(p).s("}}");
185                id
186            }
187        };
188        self.emit()?;
189        self.names[n.index()] = id;
190        Ok(id)
191    }
192
193    fn name_list(&mut self, ns: &[NameId]) -> Result<String> {
194        let ids = ns
195            .iter()
196            .map(|&n| self.name(n))
197            .collect::<Result<Vec<_>>>()?;
198        Ok(json_list(&ids))
199    }
200
201    fn level_params(&mut self, ps: &[NameId]) -> Result<String> {
202        let list = self.name_list(ps)?;
203        for &p in ps {
204            let l = self
205                .env
206                .levels
207                .get(&Level::Param(p))
208                .expect("level params are interned at load");
209            self.level(l)?;
210        }
211        Ok(list)
212    }
213
214    fn level(&mut self, l: LevelId) -> Result<u32> {
215        if self.levels[l.index()] != UNSEEN {
216            return Ok(self.levels[l.index()]);
217        }
218        let (key, a, b) = match self.env.levels[l] {
219            Level::Zero => unreachable!(),
220            Level::Succ(a) => ("succ", self.level(a)?, None),
221            Level::Max(a, b) => ("max", self.level(a)?, Some(self.level(b)?)),
222            Level::IMax(a, b) => ("imax", self.level(a)?, Some(self.level(b)?)),
223            Level::Param(n) => ("param", self.name(n)?, None),
224        };
225        let id = fresh(&mut self.next.levels);
226        let line = self
227            .start()
228            .s(r#"{"il":"#)
229            .n(id)
230            .s(r#",""#)
231            .s(key)
232            .s(r#"":"#);
233        match b {
234            None => line.n(a),
235            Some(b) => line.s("[").n(a).s(",").n(b).s("]"),
236        }
237        .s("}");
238        self.emit()?;
239        self.levels[l.index()] = id;
240        Ok(id)
241    }
242
243    fn expr(&mut self, e: ExprId) -> Result<u32> {
244        if self.exprs[e.index()] != UNSEEN {
245            return Ok(self.exprs[e.index()]);
246        }
247        let id = match &self.env.exprs[e] {
248            Expr::BVar(i) => {
249                let id = fresh(&mut self.next.exprs);
250                self.start()
251                    .s(r#"{"bvar":"#)
252                    .n(*i)
253                    .s(r#","ie":"#)
254                    .n(id)
255                    .s("}");
256                id
257            }
258            Expr::Sort(l) => {
259                let l = self.level(*l)?;
260                let id = fresh(&mut self.next.exprs);
261                self.start()
262                    .s(r#"{"ie":"#)
263                    .n(id)
264                    .s(r#","sort":"#)
265                    .n(l)
266                    .s("}");
267                id
268            }
269            Expr::Const(n, us) => {
270                let n = self.name(*n)?;
271                let us = us
272                    .iter()
273                    .map(|&u| self.level(u))
274                    .collect::<Result<Vec<_>>>()?;
275                let id = fresh(&mut self.next.exprs);
276                self.start().s(r#"{"const":{"name":"#).n(n).s(r#","us":"#);
277                self.buf.list(&us).s(r#"},"ie":"#).n(id).s("}");
278                id
279            }
280            Expr::App(f, a) => {
281                let (f, a) = (self.expr(*f)?, self.expr(*a)?);
282                let id = fresh(&mut self.next.exprs);
283                self.start().s(r#"{"app":{"arg":"#).n(a).s(r#","fn":"#).n(f);
284                self.buf.s(r#"},"ie":"#).n(id).s("}");
285                id
286            }
287            Expr::Lam(n, t, b, bi) | Expr::Pi(n, t, b, bi) => {
288                let (n, t, b) = (self.name(*n)?, self.expr(*t)?, self.expr(*b)?);
289                let id = fresh(&mut self.next.exprs);
290                let lam = matches!(self.env.exprs[e], Expr::Lam(..));
291                let line = self.start();
292                if lam {
293                    line.s(r#"{"ie":"#).n(id).s(r#","lam":"#);
294                } else {
295                    line.s(r#"{"forallE":"#);
296                }
297                line.s(r#"{"binderInfo":""#)
298                    .s(binder(*bi))
299                    .s(r#"","body":"#)
300                    .n(b);
301                line.s(r#","name":"#).n(n).s(r#","type":"#).n(t).s("}");
302                if lam {
303                    line.s("}");
304                } else {
305                    line.s(r#","ie":"#).n(id).s("}");
306                }
307                id
308            }
309            Expr::Let(n, t, v, b) => {
310                let (n, t, v, b) = (
311                    self.name(*n)?,
312                    self.expr(*t)?,
313                    self.expr(*v)?,
314                    self.expr(*b)?,
315                );
316                let id = fresh(&mut self.next.exprs);
317                self.start()
318                    .s(r#"{"ie":"#)
319                    .n(id)
320                    .s(r#","letE":{"body":"#)
321                    .n(b);
322                self.buf
323                    .s(r#","name":"#)
324                    .n(n)
325                    // Lean marks most `let`s nondep, but lean4export writes false for all of
326                    // them so that terms differing only in the flag share one index.
327                    .s(r#","nondep":false,"type":"#)
328                    .n(t);
329                self.buf.s(r#","value":"#).n(v).s("}}");
330                id
331            }
332            Expr::Nat(v) => {
333                if let Some(nat) = self.nat {
334                    self.constant(nat)?;
335                }
336                let id = fresh(&mut self.next.exprs);
337                self.start()
338                    .s(r#"{"ie":"#)
339                    .n(id)
340                    .s(r#","natVal":""#)
341                    .s(v)
342                    .s(r#""}"#);
343                id
344            }
345            Expr::Str(v) => {
346                for c in self.str_deps.into_iter().flatten() {
347                    self.constant(c)?;
348                }
349                let id = fresh(&mut self.next.exprs);
350                self.start()
351                    .s(r#"{"ie":"#)
352                    .n(id)
353                    .s(r#","strVal":"#)
354                    .q(v)
355                    .s("}");
356                id
357            }
358            Expr::Proj(n, i, x) => {
359                let (n, x) = (self.name(*n)?, self.expr(*x)?);
360                let id = fresh(&mut self.next.exprs);
361                self.start()
362                    .s(r#"{"ie":"#)
363                    .n(id)
364                    .s(r#","proj":{"idx":"#)
365                    .n(*i);
366                self.buf
367                    .s(r#","struct":"#)
368                    .n(x)
369                    .s(r#","typeName":"#)
370                    .n(n)
371                    .s("}}");
372                id
373            }
374        };
375        self.emit()?;
376        self.exprs[e.index()] = id;
377        Ok(id)
378    }
379
380    fn deps(&mut self, e: ExprId) -> Result<()> {
381        if self.scanned[e.index()] {
382            return Ok(());
383        }
384        match &self.env.exprs[e] {
385            Expr::Const(n, _) => self.constant(*n)?,
386            Expr::App(a, b) | Expr::Lam(_, a, b, _) | Expr::Pi(_, a, b, _) => {
387                self.deps(*a)?;
388                self.deps(*b)?;
389            }
390            Expr::Let(_, t, v, b) => {
391                self.deps(*t)?;
392                self.deps(*v)?;
393                self.deps(*b)?;
394            }
395            Expr::Proj(_, _, x) => self.deps(*x)?,
396            Expr::BVar(_) | Expr::Sort(_) | Expr::Nat(_) | Expr::Str(_) => {}
397        }
398        self.scanned[e.index()] = true;
399        Ok(())
400    }
401
402    /// Export a constant and, first, everything it mentions.
403    pub fn constant(&mut self, c: NameId) -> Result<()> {
404        if !self.visited.insert(c) {
405            return Ok(());
406        }
407        let env = self.env;
408        let Some(k) = env.consts.get(&c) else {
409            return Ok(());
410        };
411        match &k.kind {
412            Kind::Axiom => {
413                self.deps(k.ty)?;
414                let (n, lp, t) = self.header(k)?;
415                self.line(&format!(
416                    r#"{{"axiom":{{"isUnsafe":false,"levelParams":{lp},"name":{n},"type":{t}}}}}"#
417                ))
418            }
419            Kind::Defn(d) => {
420                self.deps(k.ty)?;
421                self.deps(d.value)?;
422                let (n, lp, t) = self.header(k)?;
423                let v = self.expr(d.value)?;
424                let all = self.name_list(&d.all)?;
425                let hints = match d.hints {
426                    Hints::Opaque => r#""opaque""#.to_owned(),
427                    Hints::Abbrev => r#""abbrev""#.to_owned(),
428                    Hints::Regular(h) => format!(r#"{{"regular":{h}}}"#),
429                };
430                self.line(&format!(
431                    r#"{{"def":{{"all":{all},"hints":{hints},"levelParams":{lp},"name":{n},"safety":"safe","type":{t},"value":{v}}}}}"#
432                ))
433            }
434            Kind::Thm(b) | Kind::Opaque(b) => {
435                self.deps(k.ty)?;
436                self.deps(b.value)?;
437                let (n, lp, t) = self.header(k)?;
438                let v = self.expr(b.value)?;
439                let all = self.name_list(&b.all)?;
440                if matches!(k.kind, Kind::Thm(_)) {
441                    self.line(&format!(r#"{{"thm":{{"all":{all},"levelParams":{lp},"name":{n},"type":{t},"value":{v}}}}}"#))
442                } else {
443                    self.line(&format!(
444                        r#"{{"opaque":{{"all":{all},"isUnsafe":false,"levelParams":{lp},"name":{n},"type":{t},"value":{v}}}}}"#
445                    ))
446                }
447            }
448            Kind::Quot(_) => self.quot(),
449            Kind::Induct(ind) => self.inductive(k, ind),
450            Kind::Ctor(ctor) => self.constant(ctor.induct),
451            Kind::Rec(rec) => rec.all.iter().try_for_each(|&i| self.constant(i)),
452        }
453    }
454
455    fn header(&mut self, k: &Const) -> Result<(u32, String, u32)> {
456        Ok((
457            self.name(k.name)?,
458            self.level_params(&k.level_params)?,
459            self.expr(k.ty)?,
460        ))
461    }
462
463    fn quot(&mut self) -> Result<()> {
464        let env = self.env;
465        let [eq, rest @ ..] = self.quot;
466        if let Some(eq) = eq {
467            self.constant(eq)?;
468        }
469        for c in rest.into_iter().flatten() {
470            self.visited.insert(c);
471            let (k, kind) = lookup(env, c, "quotient", |k| match k {
472                Kind::Quot(q) => Some(q),
473                _ => None,
474            })?;
475            let (n, lp, t) = self.header(k)?;
476            let kind = match kind {
477                QuotKind::Type => "type",
478                QuotKind::Ctor => "ctor",
479                QuotKind::Lift => "lift",
480                QuotKind::Ind => "ind",
481            };
482            self.line(&format!(
483                r#"{{"quot":{{"kind":"{kind}","levelParams":{lp},"name":{n},"type":{t}}}}}"#
484            ))?;
485        }
486        Ok(())
487    }
488
489    fn inductive(&mut self, base: &Const, ind: &Inductive) -> Result<()> {
490        let env = self.env;
491        let types = ind
492            .all
493            .iter()
494            .map(|&n| {
495                lookup(env, n, "inductive", |k| match k {
496                    Kind::Induct(i) => Some(i),
497                    _ => None,
498                })
499            })
500            .collect::<Result<Vec<_>>>()?;
501        let mut ctors = Vec::new();
502        for &(t, i) in &types {
503            for &c in &i.ctors {
504                ctors.push(lookup(env, c, "constructor", |k| match k {
505                    Kind::Ctor(c) => Some(c),
506                    _ => None,
507                })?);
508            }
509            self.visited.insert(t.name);
510            self.deps(t.ty)?;
511        }
512        for &(c, _) in &ctors {
513            self.visited.insert(c.name);
514            self.deps(c.ty)?;
515        }
516        let recs = env
517            .recursors
518            .get(&base.name)
519            .map_or(&[][..], Vec::as_slice)
520            .iter()
521            .map(|&r| {
522                lookup(env, r, "recursor", |k| match k {
523                    Kind::Rec(r) => Some(r),
524                    _ => None,
525                })
526            })
527            .collect::<Result<Vec<_>>>()?;
528        for &(r, _) in &recs {
529            self.visited.insert(r.name);
530            self.deps(r.ty)?;
531        }
532        for (_, rec) in &recs {
533            for rule in &rec.rules {
534                self.deps(rule.rhs)?;
535            }
536        }
537        let mut out = String::from(r#"{"inductive":{"ctors":["#);
538        for (i, &(c, ctor)) in ctors.iter().enumerate() {
539            let Ctor {
540                induct,
541                cidx,
542                num_params,
543                num_fields,
544            } = *ctor;
545            let (n, lp, t) = self.header(c)?;
546            let induct = self.name(induct)?;
547            sep(&mut out, i);
548            let _ = write!(
549                out,
550                r#"{{"cidx":{cidx},"induct":{induct},"isUnsafe":false,"levelParams":{lp},"name":{n},"numFields":{num_fields},"numParams":{num_params},"type":{t}}}"#
551            );
552        }
553        out.push_str(r#"],"recs":["#);
554        for (i, &(r, rec)) in recs.iter().enumerate() {
555            let Rec {
556                all,
557                num_params,
558                num_indices,
559                num_motives,
560                num_minors,
561                rules,
562                k,
563            } = rec;
564            let (n, lp, t) = self.header(r)?;
565            let all = self.name_list(all)?;
566            let mut rs = String::new();
567            for (j, rule) in rules.iter().enumerate() {
568                let (ctor, rhs) = (self.name(rule.ctor)?, self.expr(rule.rhs)?);
569                sep(&mut rs, j);
570                let _ = write!(
571                    rs,
572                    r#"{{"ctor":{ctor},"nfields":{},"rhs":{rhs}}}"#,
573                    rule.nfields
574                );
575            }
576            sep(&mut out, i);
577            let _ = write!(
578                out,
579                r#"{{"all":{all},"isUnsafe":false,"k":{k},"levelParams":{lp},"name":{n},"numIndices":{num_indices},"numMinors":{num_minors},"numMotives":{num_motives},"numParams":{num_params},"rules":[{rs}],"type":{t}}}"#
580            );
581        }
582        out.push_str(r#"],"types":["#);
583        for (i, &(ty, ind)) in types.iter().enumerate() {
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 (n, lp, t) = self.header(ty)?;
594            let (all, ctors) = (self.name_list(all)?, self.name_list(ctors)?);
595            sep(&mut out, i);
596            let _ = write!(
597                out,
598                r#"{{"all":{all},"ctors":{ctors},"isRec":{is_rec},"isReflexive":{is_reflexive},"isUnsafe":false,"levelParams":{lp},"name":{n},"numIndices":{num_indices},"numNested":{num_nested},"numParams":{num_params},"type":{t}}}"#
599            );
600        }
601        out.push_str("]}}");
602        self.line(&out)
603    }
604}
605
606/// The constant `n` and the part of its kind that `pick` selects, or an error saying it is
607/// not the `what` the referring constant claims.
608fn lookup<'e, T>(
609    env: &'e Env,
610    n: NameId,
611    what: &str,
612    pick: impl Fn(&'e Kind) -> Option<&'e T>,
613) -> Result<(&'e Const, &'e T)> {
614    env.consts
615        .get(&n)
616        .and_then(|c| Some((c, pick(&c.kind)?)))
617        .ok_or_else(|| corrupt(format!("{} is not a known {what}", env.display(n))))
618}
619
620const fn fresh(next: &mut u32) -> u32 {
621    *next += 1;
622    *next - 1
623}
624
625const fn binder(b: Binder) -> &'static str {
626    match b {
627        Binder::Default => "default",
628        Binder::Implicit => "implicit",
629        Binder::StrictImplicit => "strictImplicit",
630        Binder::InstImplicit => "instImplicit",
631    }
632}
633
634fn sep(s: &mut String, i: usize) {
635    if i > 0 {
636        s.push(',');
637    }
638}
639
640fn json_list(ids: &[u32]) -> String {
641    let mut s = String::from("[");
642    for (i, id) in ids.iter().enumerate() {
643        sep(&mut s, i);
644        let _ = write!(s, "{id}");
645    }
646    s.push(']');
647    s
648}