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