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#[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 builtins: Builtins,
61 depth: Depth,
62 scope: Option<Box<Scope>>,
63}
64
65#[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 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
137enum 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 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 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 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 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 #[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 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 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 pub fn finish(self) -> Result<S::Output> {
274 self.suspend().map(|(out, _)| out)
275 }
276
277 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 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 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 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 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 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 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}