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            .stack_size(crate::STACK)
563            .build()?;
564        let (done, consts) = (AtomicUsize::new(0), AtomicUsize::new(0));
565        let decoded = pool.install(|| {
566            found
567                .par_iter()
568                .enumerate()
569                .map_init(
570                    || None,
571                    |cursor, (rank, (_, path))| {
572                        let rank = u32::try_from(rank).expect("module count");
573                        let m = decode(&tables, rank, cursor, path)?;
574                        let n = consts.fetch_add(m.consts.len(), Relaxed) + m.consts.len();
575                        progress(done.fetch_add(1, Relaxed) + 1, n);
576                        Ok(m)
577                    },
578                )
579                .collect::<Result<Vec<_>>>()
580        })?;
581        let mut env = Self {
582            names: tables.names.freeze(),
583            levels: tables.levels.freeze(),
584            exprs: tables.exprs.freeze(),
585            consts: FxHashMap::default(),
586            order: Vec::new(),
587            recursors: FxHashMap::default(),
588            modules: Vec::new(),
589            header: Header::default(),
590            skipped: 0,
591        };
592        for ((module, _), m) in found.into_iter().zip(decoded) {
593            for c in m.consts {
594                env.order.push(c.name);
595                env.consts.insert(c.name, c);
596            }
597            for (ind, recs) in m.recursors {
598                env.recursors.entry(ind).or_default().extend(recs);
599            }
600            env.skipped += m.skipped;
601            env.header = m.header;
602            env.modules.push(module);
603        }
604        Ok(env)
605    }
606
607    /// The constants `lean4export` exports when given no explicit names.
608    pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
609        self.order.iter().copied().filter(|&c| !self.is_internal(c))
610    }
611
612    /// Look up a dotted name such as `Nat.add` without interning it.
613    #[must_use]
614    pub fn find_name(&self, dotted: &str) -> Option<NameId> {
615        dotted.split('.').try_fold(ANON, |pre, s| {
616            let n = s
617                .parse()
618                .map_or_else(|_| Name::Str(pre, s.into()), |i| Name::Num(pre, i));
619            self.names.get(&n)
620        })
621    }
622
623    #[must_use]
624    pub fn display(&self, n: NameId) -> String {
625        match &self.names[n] {
626            Name::Anon => String::new(),
627            Name::Str(ANON, s) => s.to_string(),
628            Name::Num(ANON, i) => i.to_string(),
629            Name::Str(p, s) => format!("{}.{s}", self.display(*p)),
630            Name::Num(p, i) => format!("{}.{i}", self.display(*p)),
631        }
632    }
633
634    #[must_use]
635    pub fn is_internal(&self, n: NameId) -> bool {
636        match &self.names[n] {
637            Name::Anon => false,
638            Name::Str(p, s) => s.starts_with('_') || self.is_internal(*p),
639            Name::Num(p, _) => self.is_internal(*p),
640        }
641    }
642}
643
644fn decode(tables: &Tables, rank: u32, cursor: &mut Option<usize>, path: &Path) -> Result<Module> {
645    let img = Image::open_module(path)?;
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
684/// The `.olean` for a dotted module name such as `Init.Prelude`, from the first directory
685/// of `search` that has it.
686pub fn resolve(search: &[PathBuf], module: &str) -> Result<PathBuf> {
687    let rel: PathBuf = module.split('.').collect();
688    search
689        .iter()
690        .map(|dir| dir.join(&rel).with_extension("olean"))
691        .find(|p| p.is_file())
692        .ok_or_else(|| Error::ModuleNotFound(module.to_owned()))
693}
694
695impl Image {
696    pub(crate) fn imports(&self) -> Result<Vec<String>> {
697        let imports = self.array(self.field(self.root, 0)?)?;
698        imports
699            .into_iter()
700            .map(|i| self.str_name(self.field(i, 0)?))
701            .collect()
702    }
703
704    pub(crate) fn str_name(&self, mut o: u64) -> Result<String> {
705        let mut parts = Vec::new();
706        while !is_scalar(o) && self.tag(o)? != 0 {
707            parts.push(if self.tag(o)? == 1 {
708                self.str(self.field(o, 1)?)?.to_owned()
709            } else {
710                self.nat_decimal(self.field(o, 1)?)?
711            });
712            o = self.field(o, 0)?;
713        }
714        parts.reverse();
715        Ok(parts.join("."))
716    }
717}
718
719/// Translates one module's objects into the shared tables, memoized by address since the
720/// compactor already maximally shares structurally equal objects within a module.
721struct Decoder<'a> {
722    img: &'a Image,
723    tables: &'a Tables,
724    /// The module's position in import order.
725    rank: u32,
726    /// The expression chunk this thread is filling.
727    cursor: &'a mut Option<usize>,
728    module: Module,
729    /// Table id plus one for each decoded object, by slot. An object is only ever decoded as
730    /// one of name, level or expression, so the kinds can share it.
731    memo: Vec<u32>,
732}
733
734impl Decoder<'_> {
735    fn run(&mut self) -> Result<()> {
736        let img = self.img;
737        for c in img.array(img.field(img.root, 2)?)? {
738            self.constant(c)?;
739        }
740        Ok(())
741    }
742
743    /// The memo slot of `o`, and its id if it was already decoded.
744    fn seen<T>(&self, o: u64) -> Result<(usize, Option<Id<T>>)> {
745        let slot = self.img.slot(o)?;
746        Ok((slot, self.memo[slot].checked_sub(1).map(Id::new)))
747    }
748
749    fn remember<T>(&mut self, slot: usize, id: Id<T>) -> Id<T> {
750        self.memo[slot] = id.0 + 1;
751        id
752    }
753
754    fn name(&mut self, o: u64) -> Result<NameId> {
755        let img = self.img;
756        if is_scalar(o) || img.tag(o)? == 0 {
757            return Ok(ANON);
758        }
759        let (slot, seen) = self.seen(o)?;
760        if let Some(id) = seen {
761            return Ok(id);
762        }
763        let pre = self.name(img.field(o, 0)?)?;
764        let arg = img.field(o, 1)?;
765        let n = match img.tag(o)? {
766            1 => Name::Str(pre, img.str(arg)?.into()),
767            _ => Name::Num(pre, small_nat(arg)?),
768        };
769        let id = self.tables.names.intern(n);
770        Ok(self.remember(slot, id))
771    }
772
773    fn names(&mut self, o: u64) -> Result<Vec<NameId>> {
774        self.img
775            .list(o)?
776            .into_iter()
777            .map(|n| self.name(n))
778            .collect()
779    }
780
781    fn level(&mut self, o: u64) -> Result<LevelId> {
782        let img = self.img;
783        if is_scalar(o) || img.tag(o)? == 0 {
784            return Ok(ZERO);
785        }
786        let (slot, seen) = self.seen(o)?;
787        if let Some(id) = seen {
788            return Ok(id);
789        }
790        let f = |i| img.field(o, i);
791        let l = match img.tag(o)? {
792            1 => Level::Succ(self.level(f(0)?)?),
793            2 => Level::Max(self.level(f(0)?)?, self.level(f(1)?)?),
794            3 => Level::IMax(self.level(f(0)?)?, self.level(f(1)?)?),
795            4 => Level::Param(self.name(f(0)?)?),
796            t => return Err(corrupt(format!("unexpected level tag {t}"))),
797        };
798        let id = self.tables.levels.intern(l);
799        Ok(self.remember(slot, id))
800    }
801
802    fn expr(&mut self, o: u64) -> Result<ExprId> {
803        let (slot, seen) = self.seen(o)?;
804        if let Some(id) = seen {
805            return Ok(id);
806        }
807        let img = self.img;
808        let f = |i| img.field(o, i);
809        let binder = || {
810            Ok::<_, Error>(match img.scalar_u8(o, 8)? {
811                0 => Binder::Default,
812                1 => Binder::Implicit,
813                2 => Binder::StrictImplicit,
814                _ => Binder::InstImplicit,
815            })
816        };
817        let e = match img.tag(o)? {
818            0 => Expr::BVar(small_nat(f(0)?)?),
819            3 => Expr::Sort(self.level(f(0)?)?),
820            4 => {
821                let us = img.list(f(1)?)?;
822                let us = us
823                    .into_iter()
824                    .map(|l| self.level(l))
825                    .collect::<Result<_>>()?;
826                Expr::Const(self.name(f(0)?)?, us)
827            }
828            5 => Expr::App(self.expr(f(0)?)?, self.expr(f(1)?)?),
829            6 => Expr::Lam(
830                self.name(f(0)?)?,
831                self.expr(f(1)?)?,
832                self.expr(f(2)?)?,
833                binder()?,
834            ),
835            7 => Expr::Pi(
836                self.name(f(0)?)?,
837                self.expr(f(1)?)?,
838                self.expr(f(2)?)?,
839                binder()?,
840            ),
841            8 => Expr::Let(
842                self.name(f(0)?)?,
843                self.expr(f(1)?)?,
844                self.expr(f(2)?)?,
845                self.expr(f(3)?)?,
846            ),
847            9 => {
848                let lit = f(0)?;
849                let val = img.field(lit, 0)?;
850                if img.tag(lit)? == 0 {
851                    Expr::Nat(img.nat_decimal(val)?.into())
852                } else {
853                    Expr::Str(img.str(val)?.into())
854                }
855            }
856            10 => {
857                let id = self.expr(f(1)?)?;
858                return Ok(self.remember(slot, id));
859            }
860            11 => Expr::Proj(self.name(f(0)?)?, small_nat(f(1)?)?, self.expr(f(2)?)?),
861            t => {
862                return Err(corrupt(format!(
863                    "unexpected expression tag {t} (free or meta variable in a declaration)"
864                )))
865            }
866        };
867        let id = self.tables.exprs.intern(e, self.rank, self.cursor);
868        Ok(self.remember(slot, id))
869    }
870
871    fn constant(&mut self, info: u64) -> Result<()> {
872        let img = self.img;
873        let tag = img.tag(info)?;
874        let val = img.field(info, 0)?;
875        let unsafe_flag = match tag {
876            1 => img.scalar_u8(val, 0)? != 1,
877            0 | 3 | 6 => img.scalar_u8(val, 0)? != 0,
878            5 | 7 => img.scalar_u8(val, 1)? != 0,
879            _ => false,
880        };
881        if unsafe_flag {
882            self.module.skipped += 1;
883            return Ok(());
884        }
885        let f = |i| img.field(val, i);
886        let nat = |i| small_nat(f(i)?);
887        let cv = f(0)?;
888        let name = self.name(img.field(cv, 0)?)?;
889        let level_params = self.names(img.field(cv, 1)?)?;
890        for &p in &level_params {
891            self.tables.levels.intern(Level::Param(p));
892        }
893        let ty = self.expr(img.field(cv, 2)?)?;
894        let kind = match tag {
895            0 => Kind::Axiom,
896            1 => {
897                let h = f(2)?;
898                let hints = if !is_scalar(h) {
899                    Hints::Regular(img.scalar_u32(h)?)
900                } else if h >> 1 == 0 {
901                    Hints::Opaque
902                } else {
903                    Hints::Abbrev
904                };
905                Kind::Defn(Defn {
906                    value: self.expr(f(1)?)?,
907                    hints,
908                    all: self.names(f(3)?)?,
909                })
910            }
911            2 => Kind::Thm(Body {
912                value: self.expr(f(1)?)?,
913                all: self.names(f(2)?)?,
914            }),
915            3 => Kind::Opaque(Body {
916                value: self.expr(f(1)?)?,
917                all: self.names(f(2)?)?,
918            }),
919            4 => Kind::Quot(match img.scalar_u8(val, 0)? {
920                0 => QuotKind::Type,
921                1 => QuotKind::Ctor,
922                2 => QuotKind::Lift,
923                _ => QuotKind::Ind,
924            }),
925            5 => Kind::Induct(Inductive {
926                num_params: nat(1)?,
927                num_indices: nat(2)?,
928                all: self.names(f(3)?)?,
929                ctors: self.names(f(4)?)?,
930                num_nested: nat(5)?,
931                is_rec: img.scalar_u8(val, 0)? != 0,
932                is_reflexive: img.scalar_u8(val, 2)? != 0,
933            }),
934            6 => Kind::Ctor(Ctor {
935                induct: self.name(f(1)?)?,
936                cidx: nat(2)?,
937                num_params: nat(3)?,
938                num_fields: nat(4)?,
939            }),
940            7 => {
941                let all = self.names(f(1)?)?;
942                for &ind in &all {
943                    self.module.recursors.entry(ind).or_default().push(name);
944                }
945                let mut rules = Vec::new();
946                for r in img.list(f(6)?)? {
947                    rules.push(Rule {
948                        ctor: self.name(img.field(r, 0)?)?,
949                        nfields: small_nat(img.field(r, 1)?)?,
950                        rhs: self.expr(img.field(r, 2)?)?,
951                    });
952                }
953                Kind::Rec(Rec {
954                    all,
955                    num_params: nat(2)?,
956                    num_indices: nat(3)?,
957                    num_motives: nat(4)?,
958                    num_minors: nat(5)?,
959                    rules,
960                    k: img.scalar_u8(val, 0)? != 0,
961                })
962            }
963            t => return Err(corrupt(format!("unexpected constant tag {t}"))),
964        };
965        self.module.consts.push(Const {
966            name,
967            level_params,
968            ty,
969            kind,
970        });
971        Ok(())
972    }
973}
974
975#[must_use]
976pub fn search_path() -> Vec<PathBuf> {
977    let mut dirs: Vec<PathBuf> = std::env::var_os("LEAN_PATH")
978        .map(|p| std::env::split_paths(&p).collect())
979        .unwrap_or_default();
980    if let Some(root) = std::env::var_os("LEAN_SYSROOT") {
981        dirs.push(Path::new(&root).join("lib").join("lean"));
982    }
983    dirs
984}