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::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}
63
64enum Task {
66 Const(NameId),
67 Scan(ExprId),
68 Scanned(ExprId),
69 Emit(NameId),
70}
71
72impl<'a, W: Write> Exporter<'a, Ndjson<W>> {
73 pub fn new(env: &'a Env, out: W) -> Self {
74 Self::with_sink(env, Ndjson::new(out))
75 }
76}
77
78impl<'a, S: Sink> Exporter<'a, S> {
79 pub fn with_sink(env: &'a Env, sink: S) -> Self {
80 Self::from_mark(env, sink, Mark::fresh(env))
81 }
82
83 pub fn resume(env: &'a Env, sink: S, mark: Mark) -> Result<Self> {
85 if mark.lineage != env.lineage {
86 return Err(Error::Misuse("the mark is from another environment"));
87 }
88 Ok(Self::from_mark(env, sink, mark))
89 }
90
91 fn from_mark(env: &'a Env, sink: S, mut m: Mark) -> Self {
92 m.names.resize(env.names.bound(), UNSEEN);
93 m.levels.resize(env.levels.bound(), UNSEEN);
94 m.exprs.resize(env.exprs.bound(), UNSEEN);
95 m.scanned.resize(env.exprs.bound(), false);
96 Self {
97 env,
98 sink,
99 names: m.names,
100 levels: m.levels,
101 exprs: m.exprs,
102 next: m.next,
103 scanned: m.scanned,
104 visited: m.visited,
105 builtins: Builtins::find(env),
106 depth: Depth::Full,
107 }
108 }
109
110 #[must_use]
114 pub const fn statements(mut self) -> Self {
115 self.depth = Depth::Statements;
116 self
117 }
118
119 pub fn meta(&mut self) -> Result<()> {
120 let h = &self.env.header;
121 let meta = serde_json::json!({
122 "exporter": {"name": "olean-export", "version": env!("CARGO_PKG_VERSION")},
123 "format": {"version": "3.1.0"},
124 "lean": {"githash": h.githash, "version": h.version},
125 });
126 self.sink
127 .record(None, &Record::Meta(meta.to_string().into()))
128 }
129
130 pub fn all(&mut self) -> Result<()> {
132 self.env.roots().try_for_each(|c| self.constant(c))
133 }
134
135 #[must_use]
136 pub const fn counts(&self) -> Counts {
137 self.next
138 }
139
140 pub fn finish(self) -> Result<S::Output> {
142 self.suspend().map(|(out, _)| out)
143 }
144
145 pub fn suspend(mut self) -> Result<(S::Output, Mark)> {
147 self.sink.record(None, &Record::End(self.next))?;
148 let mark = Mark {
149 lineage: self.env.lineage,
150 names: self.names,
151 levels: self.levels,
152 exprs: self.exprs,
153 scanned: self.scanned,
154 visited: self.visited,
155 next: self.next,
156 };
157 Ok((self.sink.finish()?, mark))
158 }
159
160 pub fn update(&mut self, r: &Reload) -> Result<()> {
165 for c in &r.removed {
166 self.visited.remove(c);
167 }
168 let env = self.env;
169 let again: Vec<NameId> = r
170 .consts
171 .iter()
172 .copied()
173 .filter(|c| self.visited.remove(c) | !env.is_internal(*c))
174 .collect();
175 again.into_iter().try_for_each(|c| self.constant(c))
176 }
177
178 fn name(&mut self, n: NameId) -> Result<u32> {
179 if self.names[n.index()] != UNSEEN {
180 return Ok(self.names[n.index()]);
181 }
182 let id = match &self.env.names[n] {
183 Name::Anon => unreachable!(),
184 Name::Str(p, s) => {
185 let p = self.name(*p)?;
186 self.emit(&Record::NameStr {
187 pre: p,
188 str: s.as_ref().into(),
189 })?
190 }
191 Name::Num(p, i) => {
192 let p = self.name(*p)?;
193 self.emit(&Record::NameNum { pre: p, i: *i })?
194 }
195 };
196 self.names[n.index()] = id;
197 Ok(id)
198 }
199
200 fn name_list(&mut self, ns: &[NameId]) -> Result<Vec<u32>> {
201 ns.iter().map(|&n| self.name(n)).collect()
202 }
203
204 fn level_params(&mut self, ps: &[NameId]) -> Result<Vec<u32>> {
205 let list = self.name_list(ps)?;
206 for &p in ps {
207 let l = self
208 .env
209 .levels
210 .get(&Level::Param(p))
211 .expect("level params are interned at load");
212 self.level(l)?;
213 }
214 Ok(list)
215 }
216
217 fn level(&mut self, l: LevelId) -> Result<u32> {
218 if self.levels[l.index()] != UNSEEN {
219 return Ok(self.levels[l.index()]);
220 }
221 let r = match self.env.levels[l] {
222 Level::Zero => unreachable!(),
223 Level::Succ(a) => Record::Succ(self.level(a)?),
224 Level::Max(a, b) => Record::Max(self.level(a)?, self.level(b)?),
225 Level::IMax(a, b) => Record::IMax(self.level(a)?, self.level(b)?),
226 Level::Param(n) => Record::Param(self.name(n)?),
227 };
228 let id = self.emit(&r)?;
229 self.levels[l.index()] = id;
230 Ok(id)
231 }
232
233 fn expr(&mut self, root: ExprId) -> Result<u32> {
236 let env = self.env;
237 let mut work = vec![(root, false)];
238 while let Some((e, ready)) = work.pop() {
239 if self.exprs[e.index()] != UNSEEN {
240 continue;
241 }
242 let x = &env.exprs[e];
243 if !ready {
244 work.push((e, true));
245 match x {
246 Expr::BVar(_) => {}
247 Expr::Sort(l) => {
248 self.level(*l)?;
249 }
250 Expr::Const(n, us) => {
251 self.name(*n)?;
252 us.iter().try_for_each(|&u| self.level(u).map(drop))?;
253 }
254 Expr::App(f, a) => work.extend([(*a, false), (*f, false)]),
255 Expr::Lam(n, t, b, _) | Expr::Pi(n, t, b, _) => {
256 self.name(*n)?;
257 work.extend([(*b, false), (*t, false)]);
258 }
259 Expr::Let(n, t, v, b) => {
260 self.name(*n)?;
261 work.extend([(*b, false), (*v, false), (*t, false)]);
262 }
263 Expr::Nat(_) | Expr::Str(_) => {
264 let mut lits = Vec::new();
265 self.env.children(e, &self.builtins, |d| lits.push(d));
266 for d in lits {
267 if let Dep::Literal(c) = d {
268 self.constant(c)?;
269 }
270 }
271 }
272 Expr::Proj(n, _, x) => {
273 self.name(*n)?;
274 work.push((*x, false));
275 }
276 }
277 continue;
278 }
279 let (names, levels, exprs) = (&self.names, &self.levels, &self.exprs);
280 let name = |n: &NameId| names[n.index()];
281 let level = |l: &LevelId| levels[l.index()];
282 let expr = |e: &ExprId| exprs[e.index()];
283 let bind = |n: &NameId, t: &ExprId, b: &ExprId, bi: &Binder| Binding {
284 info: *bi,
285 name: name(n),
286 ty: expr(t),
287 body: expr(b),
288 };
289 let r = match x {
290 Expr::BVar(i) => Record::BVar(*i),
291 Expr::Sort(l) => Record::Sort(level(l)),
292 Expr::Const(n, us) => Record::Const {
293 name: name(n),
294 us: us.iter().map(level).collect(),
295 },
296 Expr::App(f, a) => Record::App {
297 fun: expr(f),
298 arg: expr(a),
299 },
300 Expr::Lam(n, t, b, bi) => Record::Lam(bind(n, t, b, bi)),
301 Expr::Pi(n, t, b, bi) => Record::Pi(bind(n, t, b, bi)),
302 Expr::Let(n, t, v, b) => Record::Let {
305 name: name(n),
306 ty: expr(t),
307 value: expr(v),
308 body: expr(b),
309 nondep: false,
310 },
311 Expr::Nat(v) => Record::Nat(v.as_ref().into()),
312 Expr::Str(v) => Record::Str(v.as_ref().into()),
313 Expr::Proj(n, i, x) => Record::Proj {
314 type_name: name(n),
315 idx: *i,
316 struct_: expr(x),
317 },
318 };
319 let id = self.emit(&r)?;
320 self.exprs[e.index()] = id;
321 }
322 Ok(self.exprs[root.index()])
323 }
324
325 fn emit(&mut self, r: &Record<'_>) -> Result<u32> {
327 let id = self.next.assign(r);
328 self.sink.record(id, r)?;
329 Ok(id.expect("emit takes only id-bearing records"))
330 }
331
332 fn decl(&mut self, d: Decl) -> Result<()> {
333 self.sink.record(None, &Record::Decl(d))
334 }
335
336 pub fn constant(&mut self, c: NameId) -> Result<()> {
340 let env = self.env;
341 let mut work = vec![Task::Const(c)];
342 while let Some(task) = work.pop() {
343 match task {
344 Task::Scan(e) => {
345 if !self.scanned[e.index()] {
346 work.push(Task::Scanned(e));
347 let at = work.len();
348 env.children(e, &self.builtins, |d| match d {
349 Dep::Expr(x) => work.push(Task::Scan(x)),
350 Dep::Const(c) => work.push(Task::Const(c)),
351 Dep::Member(_) | Dep::Literal(_) | Dep::Unloaded(_) => {}
352 });
353 work[at..].reverse();
354 }
355 }
356 Task::Scanned(e) => self.scanned[e.index()] = true,
357 Task::Const(c) => {
358 if !self.visited.insert(c) {
359 continue;
360 }
361 let Some(k) = env.consts.get(&c) else {
362 continue;
363 };
364 if !matches!(k.kind, Kind::Ctor(_) | Kind::Rec(_)) {
365 work.push(Task::Emit(c));
366 }
367 let at = work.len();
368 let mut unloaded = None;
369 env.mentions(k, self.depth, &self.builtins, |d| match d {
370 Dep::Expr(e) => work.push(Task::Scan(e)),
371 Dep::Const(c) => work.push(Task::Const(c)),
372 Dep::Member(c) => {
373 self.visited.insert(c);
374 }
375 Dep::Literal(_) => {}
376 Dep::Unloaded(c) => unloaded = Some(c),
377 })?;
378 if let Some(c) = unloaded {
379 return Err(corrupt(format!(
380 "the value of {} was not loaded",
381 env.display(c)
382 )));
383 }
384 work[at..].reverse();
385 }
386 Task::Emit(c) => self.write(c)?,
387 }
388 }
389 Ok(())
390 }
391
392 fn write(&mut self, c: NameId) -> Result<()> {
394 let k = &self.env.consts[&c];
395 match &k.kind {
396 Kind::Thm(_) if self.depth == Depth::Statements => {
397 let head = self.header(k)?;
398 self.decl(Decl::Axiom {
399 head,
400 is_unsafe: false,
401 all: None,
402 })
403 }
404 Kind::Axiom => {
405 let head = self.header(k)?;
406 self.decl(Decl::Axiom {
407 head,
408 is_unsafe: false,
409 all: None,
410 })
411 }
412 Kind::Defn(d) => {
413 let head = self.header(k)?;
414 let value = self.expr(d.value)?;
415 let all = self.name_list(&d.all)?;
416 self.decl(Decl::Def {
417 head,
418 value,
419 hints: d.hints,
420 all,
421 safety: Safety::Safe,
422 })
423 }
424 Kind::Thm(t) => {
425 let head = self.header(k)?;
426 let value = self.expr(t.value.expect("scanned"))?;
427 let all = self.name_list(&t.all)?;
428 self.decl(Decl::Thm { head, value, all })
429 }
430 Kind::Opaque(b) => {
431 let head = self.header(k)?;
432 let value = self.expr(b.value)?;
433 let all = self.name_list(&b.all)?;
434 self.decl(Decl::Opaque {
435 head,
436 value,
437 is_unsafe: false,
438 all: Some(all),
439 })
440 }
441 Kind::Quot(_) => self.quot(),
442 Kind::Induct(ind) => self.inductive(k, ind),
443 Kind::Ctor(_) | Kind::Rec(_) => unreachable!("exported through their inductive"),
444 }
445 }
446
447 fn header(&mut self, k: &Const) -> Result<Head> {
448 Ok(Head {
449 name: self.name(k.name)?,
450 level_params: self.level_params(&k.level_params)?,
451 ty: self.expr(k.ty)?,
452 })
453 }
454
455 fn quot(&mut self) -> Result<()> {
456 let env = self.env;
457 let [_, rest @ ..] = self.builtins.quot;
458 for c in rest.into_iter().flatten() {
459 let (k, &kind) = env.lookup(c, "quotient", |k| match k {
460 Kind::Quot(q) => Some(q),
461 _ => None,
462 })?;
463 let head = self.header(k)?;
464 self.decl(Decl::Quot { head, kind })?;
465 }
466 Ok(())
467 }
468
469 fn inductive(&mut self, base: &Const, ind: &Inductive) -> Result<()> {
470 let Family { types, ctors, recs } = self.env.family(base, ind)?;
471 let mut out_ctors = Vec::with_capacity(ctors.len());
472 for &(c, ctor) in &ctors {
473 let Ctor {
474 induct,
475 cidx,
476 num_params,
477 num_fields,
478 } = *ctor;
479 let head = self.header(c)?;
480 out_ctors.push(IndCtor {
481 head,
482 is_unsafe: false,
483 induct: self.name(induct)?,
484 cidx,
485 num_params,
486 num_fields,
487 });
488 }
489 let mut out_recs = Vec::with_capacity(recs.len());
490 for &(r, rec) in &recs {
491 let Rec {
492 all,
493 num_params,
494 num_indices,
495 num_motives,
496 num_minors,
497 rules,
498 k,
499 } = rec;
500 let head = self.header(r)?;
501 let all = self.name_list(all)?;
502 let rules = rules
503 .iter()
504 .map(|rule| {
505 Ok(IndRule {
506 ctor: self.name(rule.ctor)?,
507 nfields: rule.nfields,
508 rhs: self.expr(rule.rhs)?,
509 })
510 })
511 .collect::<Result<Vec<_>>>()?;
512 out_recs.push(IndRec {
513 head,
514 is_unsafe: false,
515 all,
516 num_params: *num_params,
517 num_indices: *num_indices,
518 num_motives: *num_motives,
519 num_minors: *num_minors,
520 rules,
521 k: *k,
522 });
523 }
524 let mut out_types = Vec::with_capacity(types.len());
525 for &(ty, ind) in &types {
526 let Inductive {
527 num_params,
528 num_indices,
529 all,
530 ctors,
531 num_nested,
532 is_rec,
533 is_reflexive,
534 } = ind;
535 let head = self.header(ty)?;
536 let (all, ctors) = (self.name_list(all)?, self.name_list(ctors)?);
537 out_types.push(IndType {
538 head,
539 is_unsafe: false,
540 num_params: *num_params,
541 num_indices: *num_indices,
542 all,
543 ctors,
544 num_nested: *num_nested,
545 is_rec: *is_rec,
546 is_reflexive: *is_reflexive,
547 });
548 }
549 self.decl(Decl::Inductive {
550 types: out_types,
551 ctors: out_ctors,
552 recs: out_recs,
553 })
554 }
555}