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#[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 #[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#[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#[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#[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
263const 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#[derive(Debug)]
275struct Shared<T>(Vec<Mutex<Shard<T>>>);
276
277impl<T: Hash + Eq> Shared<T> {
278 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#[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 #[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 #[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
364struct 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 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 #[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#[derive(Debug)]
463pub struct Exprs(Vec<Vec<Expr>>);
464
465impl Exprs {
466 #[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 #[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
492struct Tables {
494 names: Shared<Name>,
495 levels: Shared<Level>,
496 exprs: SharedExprs,
497}
498
499struct Module {
501 consts: Vec<Const>,
502 recursors: FxHashMap<NameId, Vec<NameId>>,
503 skipped: usize,
504 header: Header,
505}
506
507#[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 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 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 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 pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
609 self.order.iter().copied().filter(|&c| !self.is_internal(c))
610 }
611
612 #[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
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
684pub 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
719struct Decoder<'a> {
722 img: &'a Image,
723 tables: &'a Tables,
724 rank: u32,
726 cursor: &'a mut Option<usize>,
728 module: Module,
729 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 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}