Skip to main content

olean_export/
env.rs

1use crate::{
2    error::{at, corrupt, Error, Result},
3    olean::{is_scalar, small_nat, Header, Image},
4};
5use hashbrown::{hash_table::Entry, HashTable};
6use parking_lot::{Mutex, MutexGuard};
7use rayon::prelude::*;
8use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet};
9use std::{
10    fmt,
11    hash::{BuildHasher, Hash},
12    marker::PhantomData,
13    path::{Path, PathBuf},
14    sync::{
15        atomic::{AtomicUsize, Ordering::Relaxed},
16        OnceLock,
17    },
18};
19
20/// The id of a `T` in its table.
21#[derive(PartialEq, Eq, Hash)]
22pub struct Id<T>(u32, PhantomData<fn() -> T>);
23
24impl<T> Id<T> {
25    const fn new(i: u32) -> Self {
26        Self(i, PhantomData)
27    }
28
29    /// The id as an index, for arrays sized by a table's `bound`.
30    #[must_use]
31    pub const fn index(self) -> usize {
32        self.0 as usize
33    }
34}
35
36impl<T> Clone for Id<T> {
37    fn clone(&self) -> Self {
38        *self
39    }
40}
41
42impl<T> Copy for Id<T> {}
43
44impl<T> fmt::Debug for Id<T> {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        write!(f, "#{}", self.0)
47    }
48}
49
50pub type NameId = Id<Name>;
51pub type LevelId = Id<Level>;
52pub type ExprId = Id<Expr>;
53
54pub const ANON: NameId = Id::new(0);
55pub const ZERO: LevelId = Id::new(0);
56
57#[derive(Debug, Clone, PartialEq, Eq, Hash)]
58pub enum Name {
59    Anon,
60    Str(NameId, Box<str>),
61    Num(NameId, u64),
62}
63
64#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
65pub enum Level {
66    Zero,
67    Succ(LevelId),
68    Max(LevelId, LevelId),
69    IMax(LevelId, LevelId),
70    Param(NameId),
71}
72
73#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
74pub enum Binder {
75    Default,
76    Implicit,
77    StrictImplicit,
78    InstImplicit,
79}
80
81/// Equality and hashing ignore binder names and annotations, matching Lean's `BEq Expr`,
82/// so terms that differ only there share one id, as they do in lean4export.
83#[derive(Debug, Clone)]
84pub enum Expr {
85    BVar(u64),
86    Sort(LevelId),
87    Const(NameId, Box<[LevelId]>),
88    App(ExprId, ExprId),
89    Lam(NameId, ExprId, ExprId, Binder),
90    Pi(NameId, ExprId, ExprId, Binder),
91    Let(NameId, ExprId, ExprId, ExprId),
92    Nat(Box<str>),
93    Str(Box<str>),
94    Proj(NameId, u64, ExprId),
95}
96
97impl PartialEq for Expr {
98    fn eq(&self, other: &Self) -> bool {
99        match (self, other) {
100            (Self::BVar(a), Self::BVar(b)) => a == b,
101            (Self::Sort(a), Self::Sort(b)) => a == b,
102            (Self::Const(n, us), Self::Const(m, vs)) => n == m && us == vs,
103            (Self::App(f, a), Self::App(g, b)) => f == g && a == b,
104            (Self::Lam(_, t, b, _), Self::Lam(_, u, c, _))
105            | (Self::Pi(_, t, b, _), Self::Pi(_, u, c, _)) => t == u && b == c,
106            (Self::Let(_, t, v, b), Self::Let(_, u, w, c)) => t == u && v == w && b == c,
107            (Self::Nat(a), Self::Nat(b)) | (Self::Str(a), Self::Str(b)) => a == b,
108            (Self::Proj(n, i, x), Self::Proj(m, j, y)) => n == m && i == j && x == y,
109            _ => false,
110        }
111    }
112}
113
114impl Eq for Expr {}
115
116impl Hash for Expr {
117    fn hash<H: std::hash::Hasher>(&self, h: &mut H) {
118        let pack = |a: u32, b: u32| u64::from(a) << 32 | u64::from(b);
119        match self {
120            Self::BVar(i) => h.write_u64(*i),
121            Self::Sort(l) => h.write_u32(l.0),
122            Self::Const(n, us) => {
123                h.write_u32(n.0);
124                us.iter().for_each(|u| h.write_u32(u.0));
125            }
126            Self::App(f, a) => h.write_u64(pack(f.0, a.0)),
127            Self::Lam(_, t, b, _) | Self::Pi(_, t, b, _) => h.write_u64(pack(t.0, b.0)),
128            Self::Let(_, t, v, b) => {
129                h.write_u64(pack(t.0, v.0));
130                h.write_u32(b.0);
131            }
132            Self::Nat(v) | Self::Str(v) => h.write(v.as_bytes()),
133            Self::Proj(n, i, x) => {
134                h.write_u64(pack(n.0, x.0));
135                h.write_u64(*i);
136            }
137        }
138        h.write_u8(self.tag());
139    }
140}
141
142impl Expr {
143    const fn tag(&self) -> u8 {
144        match self {
145            Self::BVar(_) => 0,
146            Self::Sort(_) => 1,
147            Self::Const(..) => 2,
148            Self::App(..) => 3,
149            Self::Lam(..) => 4,
150            Self::Pi(..) => 5,
151            Self::Let(..) => 6,
152            Self::Nat(_) => 7,
153            Self::Str(_) => 8,
154            Self::Proj(..) => 9,
155        }
156    }
157}
158
159#[derive(Debug, Clone, Copy)]
160pub enum Hints {
161    Opaque,
162    Abbrev,
163    Regular(u32),
164}
165
166#[derive(Debug, Clone, Copy)]
167pub enum QuotKind {
168    Type,
169    Ctor,
170    Lift,
171    Ind,
172}
173
174#[derive(Debug)]
175pub struct Rule {
176    pub ctor: NameId,
177    pub nfields: u64,
178    pub rhs: ExprId,
179}
180
181#[derive(Debug)]
182pub struct Defn {
183    pub value: ExprId,
184    pub hints: Hints,
185    pub all: Vec<NameId>,
186}
187
188/// The value of a theorem or opaque constant.
189#[derive(Debug)]
190pub struct Body {
191    pub value: ExprId,
192    pub all: Vec<NameId>,
193}
194
195#[derive(Debug)]
196pub struct Inductive {
197    pub num_params: u64,
198    pub num_indices: u64,
199    pub all: Vec<NameId>,
200    pub ctors: Vec<NameId>,
201    pub num_nested: u64,
202    pub is_rec: bool,
203    pub is_reflexive: bool,
204}
205
206#[derive(Debug)]
207pub struct Ctor {
208    pub induct: NameId,
209    pub cidx: u64,
210    pub num_params: u64,
211    pub num_fields: u64,
212}
213
214#[derive(Debug)]
215pub struct Rec {
216    pub all: Vec<NameId>,
217    pub num_params: u64,
218    pub num_indices: u64,
219    pub num_motives: u64,
220    pub num_minors: u64,
221    pub rules: Vec<Rule>,
222    pub k: bool,
223}
224
225#[derive(Debug)]
226pub enum Kind {
227    Axiom,
228    Defn(Defn),
229    Thm(Body),
230    Opaque(Body),
231    Quot(QuotKind),
232    Induct(Inductive),
233    Ctor(Ctor),
234    Rec(Rec),
235}
236
237/// A declaration the kernel would accept. Unsafe and partial ones are dropped at load time.
238#[derive(Debug)]
239pub struct Const {
240    pub name: NameId,
241    pub level_params: Vec<NameId>,
242    pub ty: ExprId,
243    pub kind: Kind,
244}
245
246const SHARDS: usize = 256;
247const CHUNK: usize = 1 << 14;
248
249#[derive(Debug)]
250struct Shard<T> {
251    nodes: Vec<T>,
252    index: HashTable<u32>,
253}
254
255fn hash<T: Hash>(t: &T) -> u64 {
256    FxBuildHasher.hash_one(t)
257}
258
259/// The shard of a hash. Fx hashes are weak in their middle bits, so mix them first.
260const fn shard_of(h: u64) -> usize {
261    (h.wrapping_mul(0x9e37_79b9_7f4a_7c15) >> 56) as usize % SHARDS
262}
263
264fn id(n: usize) -> u32 {
265    u32::try_from(n).expect("table overflow")
266}
267
268/// A hash-consing arena split into locked shards so that every decoding thread can intern
269/// into it at once.
270#[derive(Debug)]
271struct Shared<T>(Vec<Mutex<Shard<T>>>);
272
273impl<T: Hash + Eq> Shared<T> {
274    /// A table with room for about `n` nodes, whose id 0 is `zero`.
275    fn new(zero: T, n: usize) -> Self {
276        let mut shards: Vec<_> = (0..SHARDS)
277            .map(|_| Shard {
278                nodes: Vec::with_capacity(n / SHARDS),
279                index: HashTable::with_capacity(n / SHARDS),
280            })
281            .collect();
282        shards[0].index.insert_unique(hash(&zero), 0, |_| 0);
283        shards[0].nodes.push(zero);
284        Self(shards.into_iter().map(Mutex::new).collect())
285    }
286
287    fn intern(&self, t: T) -> Id<T> {
288        let h = hash(&t);
289        let k = shard_of(h);
290        let mut g = self.0[k].lock();
291        let s = &mut *g;
292        let nodes = &mut s.nodes;
293        let i = match s.index.entry(
294            h,
295            |&i| nodes[i as usize] == t,
296            |&i| hash(&nodes[i as usize]),
297        ) {
298            Entry::Occupied(e) => *e.get() as usize,
299            Entry::Vacant(e) => {
300                e.insert(id(nodes.len()));
301                nodes.push(t);
302                nodes.len() - 1
303            }
304        };
305        drop(g);
306        Id::new(id(i * SHARDS + k))
307    }
308
309    fn freeze(self) -> Table<T> {
310        Table(self.0.into_iter().map(Mutex::into_inner).collect())
311    }
312}
313
314/// A hash-consing arena: structurally equal nodes get the same id. Ids are interleaved
315/// across shards, so they are nearly but not exactly dense.
316#[derive(Debug)]
317pub struct Table<T>(Vec<Shard<T>>);
318
319impl<T: Hash + Eq> Table<T> {
320    pub fn get(&self, t: &T) -> Option<Id<T>> {
321        let h = hash(t);
322        let k = shard_of(h);
323        let s = &self.0[k];
324        let i = s.index.find(h, |&i| s.nodes[i as usize] == *t)?;
325        Some(Id::new(id(*i as usize * SHARDS + k)))
326    }
327
328    /// The number of nodes.
329    #[must_use]
330    pub fn len(&self) -> usize {
331        self.0.iter().map(|s| s.nodes.len()).sum()
332    }
333
334    #[must_use]
335    pub fn is_empty(&self) -> bool {
336        self.len() == 0
337    }
338
339    /// One past the largest id, for arrays indexed by id.
340    #[must_use]
341    pub fn bound(&self) -> usize {
342        self.0.iter().map(|s| s.nodes.len()).max().unwrap_or(0) * SHARDS
343    }
344}
345
346impl<T> std::ops::Index<Id<T>> for Table<T> {
347    type Output = T;
348    fn index(&self, i: Id<T>) -> &T {
349        let i = i.index();
350        &self.0[i % SHARDS].nodes[i / SHARDS]
351    }
352}
353
354#[derive(Debug)]
355struct Chunk {
356    nodes: Vec<Expr>,
357    ranks: Vec<u32>,
358}
359
360/// Expressions, interned through a sharded index but stored in chunks that each thread fills
361/// on its own, so that a term sits near its subterms in memory.
362///
363/// Equal terms can differ in binder names. The copy from the earliest module in import order
364/// wins, whatever order the modules were decoded in.
365struct SharedExprs {
366    index: Vec<Mutex<HashTable<u32>>>,
367    chunks: Vec<OnceLock<Box<Mutex<Chunk>>>>,
368    next: AtomicUsize,
369}
370
371impl SharedExprs {
372    fn new(n: usize) -> Self {
373        Self {
374            index: (0..SHARDS)
375                .map(|_| Mutex::new(HashTable::with_capacity(n / SHARDS)))
376                .collect(),
377            chunks: (0..=u32::MAX as usize / CHUNK)
378                .map(|_| OnceLock::new())
379                .collect(),
380            next: AtomicUsize::new(0),
381        }
382    }
383
384    fn chunk(&self, k: usize) -> MutexGuard<'_, Chunk> {
385        self.chunks[k]
386            .get()
387            .expect("chunk is published before its ids")
388            .lock()
389    }
390
391    /// Run `f` on node `i` and its rank.
392    fn with<R>(&self, i: u32, f: impl FnOnce(&mut Expr, &mut u32) -> R) -> R {
393        let i = i as usize;
394        let mut g = self.chunk(i / CHUNK);
395        let c = &mut *g;
396        let r = f(&mut c.nodes[i % CHUNK], &mut c.ranks[i % CHUNK]);
397        drop(g);
398        r
399    }
400
401    /// Intern `e` from module `rank`, adding it to the chunk `cursor` if it is new.
402    #[allow(clippy::significant_drop_tightening)]
403    fn intern(&self, e: Expr, rank: u32, cursor: &mut Option<usize>) -> ExprId {
404        let h = hash(&e);
405        let mut index = self.index[shard_of(h)].lock();
406        let entry = index.entry(
407            h,
408            |&i| self.with(i, |n, _| *n == e),
409            |&i| self.with(i, |n, _| hash(n)),
410        );
411        let i = match entry {
412            Entry::Occupied(o) => {
413                let i = *o.get();
414                self.with(i, |n, r| {
415                    if rank < *r {
416                        *n = e;
417                        *r = rank;
418                    }
419                });
420                i
421            }
422            Entry::Vacant(v) => {
423                let (k, mut c) = match cursor.map(|k| (k, self.chunk(k))) {
424                    Some((k, c)) if c.nodes.len() < CHUNK => (k, c),
425                    _ => {
426                        let k = self.next.fetch_add(1, Relaxed);
427                        self.chunks.get(k).expect("table overflow").get_or_init(|| {
428                            Box::new(Mutex::new(Chunk {
429                                nodes: Vec::with_capacity(CHUNK),
430                                ranks: Vec::with_capacity(CHUNK),
431                            }))
432                        });
433                        *cursor = Some(k);
434                        (k, self.chunk(k))
435                    }
436                };
437                let i = id(k * CHUNK + c.nodes.len());
438                c.nodes.push(e);
439                c.ranks.push(rank);
440                v.insert(i);
441                i
442            }
443        };
444        Id::new(i)
445    }
446
447    fn freeze(self) -> Exprs {
448        let n = self.next.into_inner();
449        let chunks = self.chunks.into_iter().take(n).map(|c| {
450            let c = c.into_inner().expect("chunk is published");
451            c.into_inner().nodes
452        });
453        Exprs(chunks.collect())
454    }
455}
456
457/// Expressions by id. Ids come in chunks, each filled by one decoding thread, with gaps.
458#[derive(Debug)]
459pub struct Exprs(Vec<Vec<Expr>>);
460
461impl Exprs {
462    /// The number of expressions.
463    #[must_use]
464    pub fn len(&self) -> usize {
465        self.0.iter().map(Vec::len).sum()
466    }
467
468    #[must_use]
469    pub fn is_empty(&self) -> bool {
470        self.len() == 0
471    }
472
473    /// One past the largest id, for arrays indexed by id.
474    #[must_use]
475    pub const fn bound(&self) -> usize {
476        self.0.len() * CHUNK
477    }
478}
479
480impl std::ops::Index<ExprId> for Exprs {
481    type Output = Expr;
482    fn index(&self, i: ExprId) -> &Expr {
483        let i = i.index();
484        &self.0[i / CHUNK][i % CHUNK]
485    }
486}
487
488/// The tables every module of one load interns into.
489struct Tables {
490    names: Shared<Name>,
491    levels: Shared<Level>,
492    exprs: SharedExprs,
493}
494
495/// What one module adds besides table entries.
496struct Module {
497    consts: Vec<Const>,
498    recursors: FxHashMap<NameId, Vec<NameId>>,
499    skipped: usize,
500    header: Header,
501}
502
503/// Every constant reachable from a set of root modules, in import order.
504#[derive(Debug)]
505pub struct Env {
506    pub names: Table<Name>,
507    pub levels: Table<Level>,
508    pub exprs: Exprs,
509    pub consts: FxHashMap<NameId, Const>,
510    pub order: Vec<NameId>,
511    pub recursors: FxHashMap<NameId, Vec<NameId>>,
512    pub modules: Vec<String>,
513    pub header: Header,
514    pub skipped: usize,
515}
516
517impl Env {
518    /// Load `roots` and their transitive imports, resolving modules against `search`.
519    pub fn load(search: &[PathBuf], roots: &[&str]) -> Result<Self> {
520        let jobs = std::thread::available_parallelism().map_or(1, usize::from);
521        Self::load_with(search, roots, jobs, &|_, _| {})
522    }
523
524    /// Like [`Env::load`] on `jobs` threads, calling `progress` with the number of modules
525    /// and constants decoded so far.
526    ///
527    /// Modules decode in parallel straight into shared tables, and the result is the same
528    /// for any `jobs`.
529    pub fn load_with(
530        search: &[PathBuf],
531        roots: &[&str],
532        jobs: usize,
533        progress: &(dyn Fn(usize, usize) + Sync),
534    ) -> Result<Self> {
535        let mut seen = FxHashSet::default();
536        let mut found = Vec::new();
537        for root in roots {
538            discover(search, root, &mut seen, &mut found)?;
539        }
540        // Sizing the tables up front avoids rehashing them while they grow. Across Lean and
541        // Mathlib there is about one expression per 64 bytes of olean and one name per 1200.
542        let bytes: u64 = found
543            .iter()
544            .flat_map(|(_, p)| {
545                ["olean", "olean.server", "olean.private"].map(|e| p.with_extension(e))
546            })
547            .filter_map(|p| std::fs::metadata(p).ok())
548            .map(|m| m.len())
549            .sum();
550        let estimate = |per: u64| usize::try_from(bytes / per).unwrap_or(0);
551        let tables = Tables {
552            names: Shared::new(Name::Anon, estimate(1200)),
553            levels: Shared::new(Level::Zero, 0),
554            exprs: SharedExprs::new(estimate(64)),
555        };
556        let pool = rayon::ThreadPoolBuilder::new()
557            .num_threads(jobs.max(1))
558            .stack_size(crate::STACK)
559            .build()?;
560        let (done, consts) = (AtomicUsize::new(0), AtomicUsize::new(0));
561        let decoded = pool.install(|| {
562            found
563                .par_iter()
564                .enumerate()
565                .map_init(
566                    || None,
567                    |cursor, (rank, (_, path))| {
568                        let rank = u32::try_from(rank).expect("module count");
569                        let m = decode(&tables, rank, cursor, path)?;
570                        let n = consts.fetch_add(m.consts.len(), Relaxed) + m.consts.len();
571                        progress(done.fetch_add(1, Relaxed) + 1, n);
572                        Ok(m)
573                    },
574                )
575                .collect::<Result<Vec<_>>>()
576        })?;
577        let mut env = Self {
578            names: tables.names.freeze(),
579            levels: tables.levels.freeze(),
580            exprs: tables.exprs.freeze(),
581            consts: FxHashMap::default(),
582            order: Vec::new(),
583            recursors: FxHashMap::default(),
584            modules: Vec::new(),
585            header: Header::default(),
586            skipped: 0,
587        };
588        for ((module, _), m) in found.into_iter().zip(decoded) {
589            for c in m.consts {
590                env.order.push(c.name);
591                env.consts.insert(c.name, c);
592            }
593            for (ind, recs) in m.recursors {
594                env.recursors.entry(ind).or_default().extend(recs);
595            }
596            env.skipped += m.skipped;
597            env.header = m.header;
598            env.modules.push(module);
599        }
600        Ok(env)
601    }
602
603    /// The constants `lean4export` exports when given no explicit names.
604    pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
605        self.order.iter().copied().filter(|&c| !self.is_internal(c))
606    }
607
608    /// Look up a dotted name such as `Nat.add` without interning it.
609    #[must_use]
610    pub fn find_name(&self, dotted: &str) -> Option<NameId> {
611        dotted.split('.').try_fold(ANON, |pre, s| {
612            let n = s
613                .parse()
614                .map_or_else(|_| Name::Str(pre, s.into()), |i| Name::Num(pre, i));
615            self.names.get(&n)
616        })
617    }
618
619    #[must_use]
620    pub fn display(&self, n: NameId) -> String {
621        match &self.names[n] {
622            Name::Anon => String::new(),
623            Name::Str(ANON, s) => s.to_string(),
624            Name::Num(ANON, i) => i.to_string(),
625            Name::Str(p, s) => format!("{}.{s}", self.display(*p)),
626            Name::Num(p, i) => format!("{}.{i}", self.display(*p)),
627        }
628    }
629
630    #[must_use]
631    pub fn is_internal(&self, n: NameId) -> bool {
632        match &self.names[n] {
633            Name::Anon => false,
634            Name::Str(p, s) => s.starts_with('_') || self.is_internal(*p),
635            Name::Num(p, _) => self.is_internal(*p),
636        }
637    }
638}
639
640fn decode(tables: &Tables, rank: u32, cursor: &mut Option<usize>, path: &Path) -> Result<Module> {
641    let mut img = Image::open(path)?;
642    if img.scalar_u8(img.root, 0).map_err(at(path))? == 1 {
643        img.push_part(&path.with_extension("olean.server"))?;
644        img.push_part(&path.with_extension("olean.private"))?;
645    }
646    let mut dec = Decoder {
647        img: &img,
648        tables,
649        rank,
650        cursor,
651        memo: vec![0; img.slots()],
652        module: Module {
653            consts: Vec::new(),
654            recursors: FxHashMap::default(),
655            skipped: 0,
656            header: img.header.clone(),
657        },
658    };
659    dec.run().map_err(at(path))?;
660    Ok(dec.module)
661}
662
663/// Find `module` and its imports, appending them to `out` in import order.
664fn discover(
665    search: &[PathBuf],
666    module: &str,
667    seen: &mut FxHashSet<String>,
668    out: &mut Vec<(String, PathBuf)>,
669) -> Result<()> {
670    if !seen.insert(module.to_owned()) {
671        return Ok(());
672    }
673    let path = resolve(search, module)?;
674    let img = Image::open(&path)?;
675    let imports = img.imports().map_err(at(&path))?;
676    drop(img);
677    for import in &imports {
678        discover(search, import, seen, out)?;
679    }
680    out.push((module.to_owned(), path));
681    Ok(())
682}
683
684fn resolve(search: &[PathBuf], module: &str) -> Result<PathBuf> {
685    let rel: PathBuf = module.split('.').collect();
686    search
687        .iter()
688        .map(|dir| dir.join(&rel).with_extension("olean"))
689        .find(|p| p.is_file())
690        .ok_or_else(|| Error::ModuleNotFound(module.to_owned()))
691}
692
693impl Image {
694    fn imports(&self) -> Result<Vec<String>> {
695        let imports = self.array(self.field(self.root, 0)?)?;
696        imports
697            .into_iter()
698            .map(|i| self.str_name(self.field(i, 0)?))
699            .collect()
700    }
701
702    fn str_name(&self, mut o: u64) -> Result<String> {
703        let mut parts = Vec::new();
704        while !is_scalar(o) && self.tag(o)? != 0 {
705            parts.push(if self.tag(o)? == 1 {
706                self.str(self.field(o, 1)?)?.to_owned()
707            } else {
708                self.nat_decimal(self.field(o, 1)?)?
709            });
710            o = self.field(o, 0)?;
711        }
712        parts.reverse();
713        Ok(parts.join("."))
714    }
715}
716
717/// Translates one module's objects into the shared tables, memoized by address since the
718/// compactor already maximally shares structurally equal objects within a module.
719struct Decoder<'a> {
720    img: &'a Image,
721    tables: &'a Tables,
722    /// The module's position in import order.
723    rank: u32,
724    /// The expression chunk this thread is filling.
725    cursor: &'a mut Option<usize>,
726    module: Module,
727    /// Table id plus one for each decoded object, by slot. An object is only ever decoded as
728    /// one of name, level or expression, so the kinds can share it.
729    memo: Vec<u32>,
730}
731
732impl Decoder<'_> {
733    fn run(&mut self) -> Result<()> {
734        let img = self.img;
735        for c in img.array(img.field(img.root, 2)?)? {
736            self.constant(c)?;
737        }
738        Ok(())
739    }
740
741    /// The memo slot of `o`, and its id if it was already decoded.
742    fn seen<T>(&self, o: u64) -> Result<(usize, Option<Id<T>>)> {
743        let slot = self.img.slot(o)?;
744        Ok((slot, self.memo[slot].checked_sub(1).map(Id::new)))
745    }
746
747    fn remember<T>(&mut self, slot: usize, id: Id<T>) -> Id<T> {
748        self.memo[slot] = id.0 + 1;
749        id
750    }
751
752    fn name(&mut self, o: u64) -> Result<NameId> {
753        let img = self.img;
754        if is_scalar(o) || img.tag(o)? == 0 {
755            return Ok(ANON);
756        }
757        let (slot, seen) = self.seen(o)?;
758        if let Some(id) = seen {
759            return Ok(id);
760        }
761        let pre = self.name(img.field(o, 0)?)?;
762        let arg = img.field(o, 1)?;
763        let n = match img.tag(o)? {
764            1 => Name::Str(pre, img.str(arg)?.into()),
765            _ => Name::Num(pre, small_nat(arg)?),
766        };
767        let id = self.tables.names.intern(n);
768        Ok(self.remember(slot, id))
769    }
770
771    fn names(&mut self, o: u64) -> Result<Vec<NameId>> {
772        self.img
773            .list(o)?
774            .into_iter()
775            .map(|n| self.name(n))
776            .collect()
777    }
778
779    fn level(&mut self, o: u64) -> Result<LevelId> {
780        let img = self.img;
781        if is_scalar(o) || img.tag(o)? == 0 {
782            return Ok(ZERO);
783        }
784        let (slot, seen) = self.seen(o)?;
785        if let Some(id) = seen {
786            return Ok(id);
787        }
788        let f = |i| img.field(o, i);
789        let l = match img.tag(o)? {
790            1 => Level::Succ(self.level(f(0)?)?),
791            2 => Level::Max(self.level(f(0)?)?, self.level(f(1)?)?),
792            3 => Level::IMax(self.level(f(0)?)?, self.level(f(1)?)?),
793            4 => Level::Param(self.name(f(0)?)?),
794            t => return Err(corrupt(format!("unexpected level tag {t}"))),
795        };
796        let id = self.tables.levels.intern(l);
797        Ok(self.remember(slot, id))
798    }
799
800    fn expr(&mut self, o: u64) -> Result<ExprId> {
801        let (slot, seen) = self.seen(o)?;
802        if let Some(id) = seen {
803            return Ok(id);
804        }
805        let img = self.img;
806        let f = |i| img.field(o, i);
807        let binder = || {
808            Ok::<_, Error>(match img.scalar_u8(o, 8)? {
809                0 => Binder::Default,
810                1 => Binder::Implicit,
811                2 => Binder::StrictImplicit,
812                _ => Binder::InstImplicit,
813            })
814        };
815        let e = match img.tag(o)? {
816            0 => Expr::BVar(small_nat(f(0)?)?),
817            3 => Expr::Sort(self.level(f(0)?)?),
818            4 => {
819                let us = img.list(f(1)?)?;
820                let us = us
821                    .into_iter()
822                    .map(|l| self.level(l))
823                    .collect::<Result<_>>()?;
824                Expr::Const(self.name(f(0)?)?, us)
825            }
826            5 => Expr::App(self.expr(f(0)?)?, self.expr(f(1)?)?),
827            6 => Expr::Lam(
828                self.name(f(0)?)?,
829                self.expr(f(1)?)?,
830                self.expr(f(2)?)?,
831                binder()?,
832            ),
833            7 => Expr::Pi(
834                self.name(f(0)?)?,
835                self.expr(f(1)?)?,
836                self.expr(f(2)?)?,
837                binder()?,
838            ),
839            8 => Expr::Let(
840                self.name(f(0)?)?,
841                self.expr(f(1)?)?,
842                self.expr(f(2)?)?,
843                self.expr(f(3)?)?,
844            ),
845            9 => {
846                let lit = f(0)?;
847                let val = img.field(lit, 0)?;
848                if img.tag(lit)? == 0 {
849                    Expr::Nat(img.nat_decimal(val)?.into())
850                } else {
851                    Expr::Str(img.str(val)?.into())
852                }
853            }
854            10 => {
855                let id = self.expr(f(1)?)?;
856                return Ok(self.remember(slot, id));
857            }
858            11 => Expr::Proj(self.name(f(0)?)?, small_nat(f(1)?)?, self.expr(f(2)?)?),
859            t => {
860                return Err(corrupt(format!(
861                    "unexpected expression tag {t} (free or meta variable in a declaration)"
862                )))
863            }
864        };
865        let id = self.tables.exprs.intern(e, self.rank, self.cursor);
866        Ok(self.remember(slot, id))
867    }
868
869    fn constant(&mut self, info: u64) -> Result<()> {
870        let img = self.img;
871        let tag = img.tag(info)?;
872        let val = img.field(info, 0)?;
873        let unsafe_flag = match tag {
874            1 => img.scalar_u8(val, 0)? != 1,
875            0 | 3 | 6 => img.scalar_u8(val, 0)? != 0,
876            5 | 7 => img.scalar_u8(val, 1)? != 0,
877            _ => false,
878        };
879        if unsafe_flag {
880            self.module.skipped += 1;
881            return Ok(());
882        }
883        let f = |i| img.field(val, i);
884        let nat = |i| small_nat(f(i)?);
885        let cv = f(0)?;
886        let name = self.name(img.field(cv, 0)?)?;
887        let level_params = self.names(img.field(cv, 1)?)?;
888        for &p in &level_params {
889            self.tables.levels.intern(Level::Param(p));
890        }
891        let ty = self.expr(img.field(cv, 2)?)?;
892        let kind = match tag {
893            0 => Kind::Axiom,
894            1 => {
895                let h = f(2)?;
896                let hints = if !is_scalar(h) {
897                    Hints::Regular(img.scalar_u32(h)?)
898                } else if h >> 1 == 0 {
899                    Hints::Opaque
900                } else {
901                    Hints::Abbrev
902                };
903                Kind::Defn(Defn {
904                    value: self.expr(f(1)?)?,
905                    hints,
906                    all: self.names(f(3)?)?,
907                })
908            }
909            2 => Kind::Thm(Body {
910                value: self.expr(f(1)?)?,
911                all: self.names(f(2)?)?,
912            }),
913            3 => Kind::Opaque(Body {
914                value: self.expr(f(1)?)?,
915                all: self.names(f(2)?)?,
916            }),
917            4 => Kind::Quot(match img.scalar_u8(val, 0)? {
918                0 => QuotKind::Type,
919                1 => QuotKind::Ctor,
920                2 => QuotKind::Lift,
921                _ => QuotKind::Ind,
922            }),
923            5 => Kind::Induct(Inductive {
924                num_params: nat(1)?,
925                num_indices: nat(2)?,
926                all: self.names(f(3)?)?,
927                ctors: self.names(f(4)?)?,
928                num_nested: nat(5)?,
929                is_rec: img.scalar_u8(val, 0)? != 0,
930                is_reflexive: img.scalar_u8(val, 2)? != 0,
931            }),
932            6 => Kind::Ctor(Ctor {
933                induct: self.name(f(1)?)?,
934                cidx: nat(2)?,
935                num_params: nat(3)?,
936                num_fields: nat(4)?,
937            }),
938            7 => {
939                let all = self.names(f(1)?)?;
940                for &ind in &all {
941                    self.module.recursors.entry(ind).or_default().push(name);
942                }
943                let mut rules = Vec::new();
944                for r in img.list(f(6)?)? {
945                    rules.push(Rule {
946                        ctor: self.name(img.field(r, 0)?)?,
947                        nfields: small_nat(img.field(r, 1)?)?,
948                        rhs: self.expr(img.field(r, 2)?)?,
949                    });
950                }
951                Kind::Rec(Rec {
952                    all,
953                    num_params: nat(2)?,
954                    num_indices: nat(3)?,
955                    num_motives: nat(4)?,
956                    num_minors: nat(5)?,
957                    rules,
958                    k: img.scalar_u8(val, 0)? != 0,
959                })
960            }
961            t => return Err(corrupt(format!("unexpected constant tag {t}"))),
962        };
963        self.module.consts.push(Const {
964            name,
965            level_params,
966            ty,
967            kind,
968        });
969        Ok(())
970    }
971}
972
973#[must_use]
974pub fn search_path() -> Vec<PathBuf> {
975    let mut dirs: Vec<PathBuf> = std::env::var_os("LEAN_PATH")
976        .map(|p| std::env::split_paths(&p).collect())
977        .unwrap_or_default();
978    if let Some(root) = std::env::var_os("LEAN_SYSROOT") {
979        dirs.push(Path::new(&root).join("lib").join("lean"));
980    }
981    dirs
982}