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