1use crate::{
2 env::{
3 Binder, Builtins, Const, Ctor, Dep, Depth, Env, Expr, ExprId, Family, Inductive, Kind,
4 LetNode, 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)]
75struct Scope {
76 owner: FxHashMap<NameId, u32>,
77 more: FxHashMap<NameId, Vec<u32>>,
78 whole: Vec<Vec<u64>>,
79 shown: Vec<Vec<u64>>,
80 public: Vec<Vec<u64>>,
81 module: u32,
82 interface: bool,
83 names: Vec<NameId>,
84 levels: Vec<LevelId>,
85 exprs: Vec<ExprId>,
86 scanned: Vec<ExprId>,
87 visited: Vec<NameId>,
88}
89
90const fn has(bits: &[u64], i: usize) -> bool {
91 bits[i / 64] >> (i % 64) & 1 == 1
92}
93
94fn add(bits: &mut [u64], more: &[u64], i: usize) {
95 bits.iter_mut().zip(more).for_each(|(b, m)| *b |= m);
96 bits[i / 64] |= 1 << (i % 64);
97}
98
99impl Scope {
100 fn new(env: &Env, restricted: bool) -> Self {
101 let mut s = Self::default();
102 for m in 0..env.modules.len() {
103 let m32 = u32::try_from(m).expect("module count");
104 for &c in env.module_consts(m) {
105 if let Some(&o) = s.owner.get(&c) {
106 if o != m32 {
107 s.more.entry(c).or_default().push(m32);
108 }
109 } else {
110 s.owner.insert(c, m32);
111 }
112 }
113 }
114 let index: FxHashMap<&str, usize> = env
115 .modules
116 .iter()
117 .enumerate()
118 .map(|(i, m)| (m.as_str(), i))
119 .collect();
120 let words = env.modules.len().div_ceil(64);
121 let mut under: Vec<Vec<u64>> = Vec::new();
122 for (m, imports) in env.imports.iter().enumerate() {
123 let module = restricted && env.exported[m].is_some();
124 let [mut all, mut whole, mut shown, mut public] = [(); 4].map(|()| vec![0u64; words]);
125 for i in imports {
126 let Some(&j) = index.get(i.module.as_str()).filter(|&&j| j < m) else {
127 continue;
128 };
129 add(&mut all, &under[j], j);
130 if module && i.all {
131 add(&mut whole, &s.whole[j], j);
132 shown.iter_mut().zip(&s.shown[j]).for_each(|(b, m)| *b |= m);
133 } else if module {
134 add(&mut shown, &s.public[j], j);
135 }
136 if i.exported {
137 add(&mut public, &s.public[j], j);
138 }
139 }
140 s.whole.push(if module { whole } else { all.clone() });
141 s.shown.push(shown);
142 s.public.push(public);
143 under.push(all);
144 }
145 s
146 }
147
148 fn writes(&self, env: &Env, c: NameId) -> bool {
150 let Some(&first) = self.owner.get(&c) else {
151 return true;
152 };
153 let owners = std::iter::once(first).chain(self.more.get(&c).into_iter().flatten().copied());
154 let m = self.module as usize;
155 let mut provided = false;
156 for o in owners {
157 if o == self.module {
158 return true;
159 }
160 let o = o as usize;
161 let shows = || env.exported[o].as_ref().is_none_or(|e| e.contains_key(&c));
162 provided |= if self.interface {
163 has(&self.public[m], o) && shows()
164 } else {
165 has(&self.whole[m], o) || has(&self.shown[m], o) && shows()
166 };
167 }
168 !provided
169 }
170}
171
172enum Task {
174 Const(NameId),
175 Scan(ExprId),
176 Scanned(ExprId),
177 Emit(NameId),
178}
179
180impl<'a, W: Write> Exporter<'a, Ndjson<W>> {
181 pub fn new(env: &'a Env, out: W) -> Self {
182 Self::with_sink(env, Ndjson::new(out))
183 }
184}
185
186impl<'a, S: Sink> Exporter<'a, S> {
187 pub fn with_sink(env: &'a Env, sink: S) -> Self {
188 Self::from_mark(env, sink, Mark::fresh(env))
189 }
190
191 pub fn resume(env: &'a Env, sink: S, mark: Mark) -> Result<Self> {
193 if mark.lineage != env.lineage {
194 return Err(Error::Misuse("the mark is from another environment"));
195 }
196 Ok(Self::from_mark(env, sink, mark))
197 }
198
199 fn from_mark(env: &'a Env, sink: S, mut m: Mark) -> Self {
200 m.names.resize(env.names.bound(), UNSEEN);
201 m.levels.resize(env.levels.bound(), UNSEEN);
202 m.exprs.resize(env.exprs.bound(), UNSEEN);
203 m.scanned.resize(env.exprs.bound(), false);
204 Self {
205 env,
206 sink,
207 names: m.names,
208 levels: m.levels,
209 exprs: m.exprs,
210 next: m.next,
211 scanned: m.scanned,
212 visited: m.visited,
213 builtins: Builtins::find(env),
214 depth: Depth::Full,
215 scope: None,
216 }
217 }
218
219 pub fn per_module(env: &'a Env, sink: S) -> Self {
223 let mut ex = Self::with_sink(env, sink);
224 ex.scope = Some(Box::new(Scope::new(env, false)));
225 ex
226 }
227
228 pub fn restricted(env: &'a Env, sink: S) -> Self {
230 let mut ex = Self::with_sink(env, sink);
231 ex.scope = Some(Box::new(Scope::new(env, true)));
232 ex
233 }
234
235 pub fn module(&mut self, m: usize) -> Result<()> {
238 self.enter(m, false)?;
239 let env = self.env;
240 env.module_consts(m)
241 .iter()
242 .try_for_each(|&c| self.constant(c))
243 }
244
245 pub fn interface(&mut self, m: usize) -> Result<()> {
247 self.enter(m, true)?;
248 let env = self.env;
249 let shown = env.exported[m].as_ref();
250 env.module_consts(m)
251 .iter()
252 .filter(|c| shown.is_none_or(|e| e.contains_key(c)))
253 .try_for_each(|&c| self.constant(c))
254 }
255
256 fn enter(&mut self, m: usize, interface: bool) -> Result<()> {
257 let s = self
258 .scope
259 .as_mut()
260 .ok_or(Error::Misuse("module needs a per-module exporter"))?;
261 s.module = u32::try_from(m).expect("module count");
262 s.interface = interface;
263 Ok(())
264 }
265
266 pub fn inside(&self, m: usize) -> impl Iterator<Item = usize> + '_ {
268 let whole = self.scope.as_ref().map(|s| &s.whole[m]);
269 (0..self.env.modules.len()).filter(move |&o| whole.is_some_and(|w| has(w, o)))
270 }
271
272 fn hidden(&self, k: &Const) -> bool {
276 let Some(s) = self.scope.as_ref().filter(|s| s.interface) else {
277 return false;
278 };
279 match k.kind {
280 Kind::Thm(_) => true,
281 Kind::Defn(_) | Kind::Opaque(_) => {
282 let owner = s.owner.get(&k.name).map(|&o| o as usize);
283 let shown = owner.and_then(|o| self.env.exported[o].as_ref());
284 shown.is_some_and(|e| e.get(&k.name) != Some(&false))
285 }
286 _ => false,
287 }
288 }
289
290 pub fn split(&mut self, sink: S) -> Result<S::Output> {
293 let s = self
294 .scope
295 .as_mut()
296 .ok_or(Error::Misuse("split needs a per-module exporter"))?;
297 for n in s.names.drain(..) {
298 self.names[n.index()] = UNSEEN;
299 }
300 for l in s.levels.drain(..) {
301 self.levels[l.index()] = UNSEEN;
302 }
303 for e in s.exprs.drain(..) {
304 self.exprs[e.index()] = UNSEEN;
305 }
306 for e in s.scanned.drain(..) {
307 self.scanned[e.index()] = false;
308 }
309 for c in s.visited.drain(..) {
310 self.visited.remove(&c);
311 }
312 self.sink.record(None, &Record::End(self.next))?;
313 self.next = Counts::default();
314 std::mem::replace(&mut self.sink, sink).finish()
315 }
316
317 #[must_use]
321 pub const fn statements(mut self) -> Self {
322 self.depth = Depth::Statements;
323 self
324 }
325
326 pub fn meta(&mut self) -> Result<()> {
327 self.meta_with(None)
328 }
329
330 pub fn meta_with(&mut self, module: Option<serde_json::Value>) -> Result<()> {
332 let h = &self.env.header;
333 let mut meta = serde_json::json!({
334 "exporter": {"name": "olean-export", "version": env!("CARGO_PKG_VERSION")},
335 "format": {"version": "3.1.0"},
336 "lean": {"githash": h.githash, "version": h.version},
337 });
338 if let Some(m) = module {
339 meta["module"] = m;
340 }
341 self.sink
342 .record(None, &Record::Meta(meta.to_string().into()))
343 }
344
345 pub fn all(&mut self) -> Result<()> {
347 self.env.roots().try_for_each(|c| self.constant(c))
348 }
349
350 #[must_use]
351 pub const fn counts(&self) -> Counts {
352 self.next
353 }
354
355 pub fn finish(self) -> Result<S::Output> {
357 self.suspend().map(|(out, _)| out)
358 }
359
360 pub fn suspend(mut self) -> Result<(S::Output, Mark)> {
362 self.sink.record(None, &Record::End(self.next))?;
363 let mark = Mark {
364 lineage: self.env.lineage,
365 names: self.names,
366 levels: self.levels,
367 exprs: self.exprs,
368 scanned: self.scanned,
369 visited: self.visited,
370 next: self.next,
371 };
372 Ok((self.sink.finish()?, mark))
373 }
374
375 pub fn update(&mut self, r: &Reload) -> Result<()> {
380 for c in &r.removed {
381 self.visited.remove(c);
382 }
383 let env = self.env;
384 let again: Vec<NameId> = r
385 .consts
386 .iter()
387 .copied()
388 .filter(|c| self.visited.remove(c) | !env.is_internal(*c))
389 .collect();
390 again.into_iter().try_for_each(|c| self.constant(c))
391 }
392
393 fn name(&mut self, n: NameId) -> Result<u32> {
394 if self.names[n.index()] != UNSEEN {
395 return Ok(self.names[n.index()]);
396 }
397 let id = match &self.env.names[n] {
398 Name::Anon => unreachable!(),
399 Name::Str(p, s) => {
400 let p = self.name(*p)?;
401 self.emit(&Record::NameStr {
402 pre: p,
403 str: s.as_ref().into(),
404 })?
405 }
406 Name::Num(p, i) => {
407 let p = self.name(*p)?;
408 self.emit(&Record::NameNum { pre: p, i: *i })?
409 }
410 };
411 self.names[n.index()] = id;
412 if let Some(s) = &mut self.scope {
413 s.names.push(n);
414 }
415 Ok(id)
416 }
417
418 fn name_list(&mut self, ns: &[NameId]) -> Result<Vec<u32>> {
419 ns.iter().map(|&n| self.name(n)).collect()
420 }
421
422 fn level_params(&mut self, ps: &[NameId]) -> Result<Vec<u32>> {
423 let list = self.name_list(ps)?;
424 for &p in ps {
425 let l = self
426 .env
427 .levels
428 .get(&Level::Param(p))
429 .expect("level params are interned at load");
430 self.level(l)?;
431 }
432 Ok(list)
433 }
434
435 fn level(&mut self, l: LevelId) -> Result<u32> {
436 if self.levels[l.index()] != UNSEEN {
437 return Ok(self.levels[l.index()]);
438 }
439 let r = match self.env.levels[l] {
440 Level::Zero => unreachable!(),
441 Level::Succ(a) => Record::Succ(self.level(a)?),
442 Level::Max(a, b) => Record::Max(self.level(a)?, self.level(b)?),
443 Level::IMax(a, b) => Record::IMax(self.level(a)?, self.level(b)?),
444 Level::Param(n) => Record::Param(self.name(n)?),
445 };
446 let id = self.emit(&r)?;
447 self.levels[l.index()] = id;
448 if let Some(s) = &mut self.scope {
449 s.levels.push(l);
450 }
451 Ok(id)
452 }
453
454 fn expr(&mut self, root: ExprId) -> Result<u32> {
457 let env = self.env;
458 let mut work = vec![(root, false)];
459 while let Some((e, ready)) = work.pop() {
460 if self.exprs[e.index()] != UNSEEN {
461 continue;
462 }
463 let x = &env.exprs[e];
464 if !ready {
465 work.push((e, true));
466 match x {
467 Expr::BVar(_) => {}
468 Expr::Sort(l) => {
469 self.level(*l)?;
470 }
471 Expr::Const(n, us) => {
472 self.name(*n)?;
473 env.univs[*us]
474 .0
475 .iter()
476 .try_for_each(|&u| self.level(u).map(drop))?;
477 }
478 Expr::App(f, a) => work.extend([(*a, false), (*f, false)]),
479 Expr::Lam(n, t, b, _) | Expr::Pi(n, t, b, _) => {
480 self.name(*n)?;
481 work.extend([(*b, false), (*t, false)]);
482 }
483 Expr::Let(l) => {
484 let LetNode(n, t, v, b) = **l;
485 self.name(n)?;
486 work.extend([(b, false), (v, false), (t, false)]);
487 }
488 Expr::Nat(_) | Expr::Str(_) => {
489 let mut lits = Vec::new();
490 self.env.children(e, &self.builtins, |d| lits.push(d));
491 for d in lits {
492 if let Dep::Literal(c) = d {
493 self.constant(c)?;
494 }
495 }
496 }
497 Expr::Proj(n, _, x) => {
498 self.name(*n)?;
499 work.push((*x, false));
500 }
501 }
502 continue;
503 }
504 let (names, levels, exprs) = (&self.names, &self.levels, &self.exprs);
505 let name = |n: &NameId| names[n.index()];
506 let level = |l: &LevelId| levels[l.index()];
507 let expr = |e: &ExprId| exprs[e.index()];
508 let bind = |n: &NameId, t: &ExprId, b: &ExprId, bi: &Binder| Binding {
509 info: *bi,
510 name: name(n),
511 ty: expr(t),
512 body: expr(b),
513 };
514 let r = match x {
515 Expr::BVar(i) => Record::BVar(*i),
516 Expr::Sort(l) => Record::Sort(level(l)),
517 Expr::Const(n, us) => Record::Const {
518 name: name(n),
519 us: env.univs[*us].0.iter().map(level).collect(),
520 },
521 Expr::App(f, a) => Record::App {
522 fun: expr(f),
523 arg: expr(a),
524 },
525 Expr::Lam(n, t, b, bi) => Record::Lam(bind(n, t, b, bi)),
526 Expr::Pi(n, t, b, bi) => Record::Pi(bind(n, t, b, bi)),
527 Expr::Let(l) => Record::Let {
530 name: name(&l.0),
531 ty: expr(&l.1),
532 value: expr(&l.2),
533 body: expr(&l.3),
534 nondep: false,
535 },
536 Expr::Nat(v) => Record::Nat((**v).as_ref().into()),
537 Expr::Str(v) => Record::Str((**v).as_ref().into()),
538 Expr::Proj(n, i, x) => Record::Proj {
539 type_name: name(n),
540 idx: u64::from(*i),
541 struct_: expr(x),
542 },
543 };
544 let id = self.emit(&r)?;
545 self.exprs[e.index()] = id;
546 if let Some(s) = &mut self.scope {
547 s.exprs.push(e);
548 }
549 }
550 Ok(self.exprs[root.index()])
551 }
552
553 fn emit(&mut self, r: &Record<'_>) -> Result<u32> {
555 let id = self.next.assign(r);
556 self.sink.record(id, r)?;
557 Ok(id.expect("emit takes only id-bearing records"))
558 }
559
560 fn decl(&mut self, d: Decl) -> Result<()> {
561 self.sink.record(None, &Record::Decl(d))
562 }
563
564 pub fn constant(&mut self, c: NameId) -> Result<()> {
568 let env = self.env;
569 let mut work = vec![Task::Const(c)];
570 let mut members = Vec::new();
571 while let Some(task) = work.pop() {
572 match task {
573 Task::Scan(e) => {
574 if !self.scanned[e.index()] {
575 work.push(Task::Scanned(e));
576 let at = work.len();
577 env.children(e, &self.builtins, |d| match d {
578 Dep::Expr(x) => work.push(Task::Scan(x)),
579 Dep::Const(c) => work.push(Task::Const(c)),
580 Dep::Member(_) | Dep::Literal(_) | Dep::Unloaded(_) => {}
581 });
582 work[at..].reverse();
583 }
584 }
585 Task::Scanned(e) => {
586 self.scanned[e.index()] = true;
587 if let Some(s) = &mut self.scope {
588 s.scanned.push(e);
589 }
590 }
591 Task::Const(c) => {
592 if self.scope.as_ref().is_some_and(|s| !s.writes(env, c)) {
593 continue;
594 }
595 if !self.visit(c) {
596 continue;
597 }
598 let Some(k) = env.consts.get(&c) else {
599 continue;
600 };
601 if !matches!(k.kind, Kind::Ctor(_) | Kind::Rec(_)) {
602 work.push(Task::Emit(c));
603 }
604 if self.hidden(k) {
605 work.push(Task::Scan(k.ty));
606 continue;
607 }
608 let at = work.len();
609 let mut unloaded = None;
610 env.mentions(k, self.depth, &self.builtins, |d| match d {
611 Dep::Expr(e) => work.push(Task::Scan(e)),
612 Dep::Const(c) => work.push(Task::Const(c)),
613 Dep::Member(c) => members.push(c),
614 Dep::Literal(_) => {}
615 Dep::Unloaded(c) => unloaded = Some(c),
616 })?;
617 if let Some(c) = unloaded {
618 return Err(corrupt(format!(
619 "the value of {} was not loaded",
620 env.display(c)
621 )));
622 }
623 work[at..].reverse();
624 for c in std::mem::take(&mut members) {
625 self.visit(c);
626 }
627 }
628 Task::Emit(c) => self.write(c)?,
629 }
630 }
631 Ok(())
632 }
633
634 fn visit(&mut self, c: NameId) -> bool {
635 let new = self.visited.insert(c);
636 if let Some(s) = self.scope.as_mut().filter(|_| new) {
637 s.visited.push(c);
638 }
639 new
640 }
641
642 fn write(&mut self, c: NameId) -> Result<()> {
644 let k = &self.env.consts[&c];
645 match &k.kind {
646 Kind::Thm(_) if self.depth == Depth::Statements => self.axiom(k),
647 _ if self.hidden(k) => self.axiom(k),
648 Kind::Axiom => self.axiom(k),
649 Kind::Defn(d) => {
650 let head = self.header(k)?;
651 let value = self.expr(d.value)?;
652 let all = self.name_list(&d.all)?;
653 self.decl(Decl::Def {
654 head,
655 value,
656 hints: d.hints,
657 all,
658 safety: Safety::Safe,
659 })
660 }
661 Kind::Thm(t) => {
662 let head = self.header(k)?;
663 let value = self.expr(t.value.expect("scanned"))?;
664 let all = self.name_list(&t.all)?;
665 self.decl(Decl::Thm { head, value, all })
666 }
667 Kind::Opaque(b) => {
668 let head = self.header(k)?;
669 let value = self.expr(b.value)?;
670 let all = self.name_list(&b.all)?;
671 self.decl(Decl::Opaque {
672 head,
673 value,
674 is_unsafe: false,
675 all: Some(all),
676 })
677 }
678 Kind::Quot(_) => self.quot(),
679 Kind::Induct(ind) => self.inductive(k, ind),
680 Kind::Ctor(_) | Kind::Rec(_) => unreachable!("exported through their inductive"),
681 }
682 }
683
684 fn axiom(&mut self, k: &Const) -> Result<()> {
685 let head = self.header(k)?;
686 self.decl(Decl::Axiom {
687 head,
688 is_unsafe: false,
689 all: None,
690 })
691 }
692
693 fn header(&mut self, k: &Const) -> Result<Head> {
694 Ok(Head {
695 name: self.name(k.name)?,
696 level_params: self.level_params(&k.level_params)?,
697 ty: self.expr(k.ty)?,
698 })
699 }
700
701 fn quot(&mut self) -> Result<()> {
702 let env = self.env;
703 let [_, rest @ ..] = self.builtins.quot;
704 for c in rest.into_iter().flatten() {
705 let (k, &kind) = env.lookup(c, "quotient", |k| match k {
706 Kind::Quot(q) => Some(q),
707 _ => None,
708 })?;
709 let head = self.header(k)?;
710 self.decl(Decl::Quot { head, kind })?;
711 }
712 Ok(())
713 }
714
715 fn inductive(&mut self, base: &Const, ind: &Inductive) -> Result<()> {
716 let Family { types, ctors, recs } = self.env.family(base, ind)?;
717 let mut out_ctors = Vec::with_capacity(ctors.len());
718 for &(c, ctor) in &ctors {
719 let Ctor {
720 induct,
721 cidx,
722 num_params,
723 num_fields,
724 } = *ctor;
725 let head = self.header(c)?;
726 out_ctors.push(IndCtor {
727 head,
728 is_unsafe: false,
729 induct: self.name(induct)?,
730 cidx,
731 num_params,
732 num_fields,
733 });
734 }
735 let mut out_recs = Vec::with_capacity(recs.len());
736 for &(r, rec) in &recs {
737 let Rec {
738 all,
739 num_params,
740 num_indices,
741 num_motives,
742 num_minors,
743 rules,
744 k,
745 } = rec;
746 let head = self.header(r)?;
747 let all = self.name_list(all)?;
748 let rules = rules
749 .iter()
750 .map(|rule| {
751 Ok(IndRule {
752 ctor: self.name(rule.ctor)?,
753 nfields: rule.nfields,
754 rhs: self.expr(rule.rhs)?,
755 })
756 })
757 .collect::<Result<Vec<_>>>()?;
758 out_recs.push(IndRec {
759 head,
760 is_unsafe: false,
761 all,
762 num_params: *num_params,
763 num_indices: *num_indices,
764 num_motives: *num_motives,
765 num_minors: *num_minors,
766 rules,
767 k: *k,
768 });
769 }
770 let mut out_types = Vec::with_capacity(types.len());
771 for &(ty, ind) in &types {
772 let Inductive {
773 num_params,
774 num_indices,
775 all,
776 ctors,
777 num_nested,
778 is_rec,
779 is_reflexive,
780 } = ind;
781 let head = self.header(ty)?;
782 let (all, ctors) = (self.name_list(all)?, self.name_list(ctors)?);
783 out_types.push(IndType {
784 head,
785 is_unsafe: false,
786 num_params: *num_params,
787 num_indices: *num_indices,
788 all,
789 ctors,
790 num_nested: *num_nested,
791 is_rec: *is_rec,
792 is_reflexive: *is_reflexive,
793 });
794 }
795 self.decl(Decl::Inductive {
796 types: out_types,
797 ctors: out_ctors,
798 recs: out_recs,
799 })
800 }
801}