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