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#[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#[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
65enum Task {
67 Const(NameId),
68 Scan(ExprId),
69 Scanned(ExprId),
70 Emit(NameId),
71}
72
73struct 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 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 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 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 pub fn finish(self) -> Result<S::Output> {
167 self.suspend().map(|(out, _)| out)
168 }
169
170 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 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 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 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 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 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 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 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
615fn 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}