Skip to main content

olean_export/
export.rs

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/// Where an export stopped, so that a later one on the same [`Env`], reloaded or not,
18/// continues its ids and writes only records the earlier one did not.
19#[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/// Streams an [`Env`] in lean4export 3.1.0 order to a [`Sink`], NDJSON by default. Ids are
49/// assigned on first use and every record only refers to records already written.
50#[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/// Per-module export: which modules declare each constant, what each module imports
66/// transitively, the module being written, and the entries its file took, to clear before
67/// the next. Lean realizes some constants, such as equation lemmas, in every module that
68/// needs them, and the environment keeps one copy, which may refer to private constants of
69/// a module the writer does not import. So a file holds what its module declares and
70/// whatever else it needs that no import provides.
71///
72/// Per module: `whole` are the modules it sees all of, `shown` those it sees the exports
73/// of, `public` those its own interface may refer to.
74#[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    /// Whether the file being written writes `c`, rather than an import providing it.
149    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
172/// One step of [`Exporter::constant`]'s depth-first walk over dependencies.
173enum 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    /// Continue the export `mark` was taken from, on the same environment.
192    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    /// An exporter that writes one module at a time with [`Exporter::module`], each to its
220    /// own sink after [`Exporter::split`]. A module's records refer to what its imports
221    /// declare by name only.
222    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    /// Like [`Exporter::per_module`], but an import provides only what Lean showed of it.
229    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    /// Write every constant module `m` declares. Internal ones are included, since a later
236    /// module may need them.
237    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    /// Write what module `m` exports.
246    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    /// The modules `m` sees all of.
267    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    /// Whether an interface states `k` as an axiom. Every theorem is, since Lean exports
273    /// some with a proof that rests on a hidden body, and so is any definition whose body
274    /// is not exported, including one an exported statement mentions but no module shows.
275    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    /// End the current file and start the next on `sink`, with ids from the start again.
291    /// Returns the finished sink's output.
292    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    /// Write every theorem as an axiom over its type, so an environment from
318    /// [`Env::load_statements`] exports its statements and what they rest on, with no
319    /// proofs.
320    #[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    /// The `meta` record, with `module` added under that key when given.
331    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    /// Export every non-internal constant in load order, like `lean4export` with no `--`.
346    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    /// Write the end record and hand back the sink's output.
356    pub fn finish(self) -> Result<S::Output> {
357        self.suspend().map(|(out, _)| out)
358    }
359
360    /// Like [`Exporter::finish`], with a [`Mark`] to [`Exporter::resume`] from.
361    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    /// After [`Env::reload`], export the reloaded constants again as [`Exporter::all`] would.
376    /// The end record counts every record since the first export.
377    /// An internal constant is written again if it was written before, since terms
378    /// already scanned will not lead back to it.
379    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    /// Export `root` after its subterms. The worklist visits each term twice: first to
455    /// export the names and levels it mentions and queue its subterms, then to write it.
456    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                // Lean marks most `let`s nondep, but lean4export writes false for all of
528                // them so that terms differing only in the flag share one index.
529                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    /// Write a name, level or expression record and return its id.
554    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    /// Export a constant and, first, everything it mentions. Dependencies are walked
565    /// depth-first on an explicit stack, so no term depth or dependency chain can overflow
566    /// the thread's stack.
567    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    /// Write the declaration of `c`, whose dependencies are already out.
643    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}