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