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 .build()?;
563 let (done, consts) = (AtomicUsize::new(0), AtomicUsize::new(0));
564 let decoded = pool.install(|| {
565 found
566 .par_iter()
567 .enumerate()
568 .map_init(
569 || None,
570 |cursor, (rank, (_, path))| {
571 let rank = u32::try_from(rank).expect("module count");
572 let m = decode(&tables, rank, cursor, path)?;
573 let n = consts.fetch_add(m.consts.len(), Relaxed) + m.consts.len();
574 progress(done.fetch_add(1, Relaxed) + 1, n);
575 Ok(m)
576 },
577 )
578 .collect::<Result<Vec<_>>>()
579 })?;
580 let mut env = Self {
581 names: tables.names.freeze(),
582 levels: tables.levels.freeze(),
583 exprs: tables.exprs.freeze(),
584 consts: FxHashMap::default(),
585 order: Vec::new(),
586 recursors: FxHashMap::default(),
587 modules: Vec::new(),
588 header: Header::default(),
589 skipped: 0,
590 };
591 for ((module, _), m) in found.into_iter().zip(decoded) {
592 for c in m.consts {
593 env.order.push(c.name);
594 env.consts.insert(c.name, c);
595 }
596 for (ind, recs) in m.recursors {
597 env.recursors.entry(ind).or_default().extend(recs);
598 }
599 env.skipped += m.skipped;
600 env.header = m.header;
601 env.modules.push(module);
602 }
603 Ok(env)
604 }
605
606 pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
608 self.order.iter().copied().filter(|&c| !self.is_internal(c))
609 }
610
611 #[must_use]
613 pub fn find_name(&self, dotted: &str) -> Option<NameId> {
614 dotted.split('.').try_fold(ANON, |pre, s| {
615 let n = s
616 .parse()
617 .map_or_else(|_| Name::Str(pre, s.into()), |i| Name::Num(pre, i));
618 self.names.get(&n)
619 })
620 }
621
622 #[must_use]
623 pub fn display(&self, n: NameId) -> String {
624 match &self.names[n] {
625 Name::Anon => String::new(),
626 Name::Str(ANON, s) => s.to_string(),
627 Name::Num(ANON, i) => i.to_string(),
628 Name::Str(p, s) => format!("{}.{s}", self.display(*p)),
629 Name::Num(p, i) => format!("{}.{i}", self.display(*p)),
630 }
631 }
632
633 #[must_use]
634 pub fn is_internal(&self, n: NameId) -> bool {
635 match &self.names[n] {
636 Name::Anon => false,
637 Name::Str(p, s) => s.starts_with('_') || self.is_internal(*p),
638 Name::Num(p, _) => self.is_internal(*p),
639 }
640 }
641}
642
643fn decode(tables: &Tables, rank: u32, cursor: &mut Option<usize>, path: &Path) -> Result<Module> {
644 let img = Image::open_module(path)?;
645 let mut dec = Decoder {
646 img: &img,
647 tables,
648 rank,
649 cursor,
650 memo: vec![0; img.slots()],
651 module: Module {
652 consts: Vec::new(),
653 recursors: FxHashMap::default(),
654 skipped: 0,
655 header: img.header.clone(),
656 },
657 };
658 dec.run().map_err(at(path))?;
659 Ok(dec.module)
660}
661
662fn discover(
664 search: &[PathBuf],
665 module: &str,
666 seen: &mut FxHashSet<String>,
667 out: &mut Vec<(String, PathBuf)>,
668) -> Result<()> {
669 if !seen.insert(module.to_owned()) {
670 return Ok(());
671 }
672 let path = resolve(search, module)?;
673 let img = Image::open(&path)?;
674 let imports = img.imports().map_err(at(&path))?;
675 drop(img);
676 for import in &imports {
677 discover(search, import, seen, out)?;
678 }
679 out.push((module.to_owned(), path));
680 Ok(())
681}
682
683pub fn resolve(search: &[PathBuf], module: &str) -> Result<PathBuf> {
686 let rel: PathBuf = module.split('.').collect();
687 search
688 .iter()
689 .map(|dir| dir.join(&rel).with_extension("olean"))
690 .find(|p| p.is_file())
691 .ok_or_else(|| Error::ModuleNotFound(module.to_owned()))
692}
693
694impl Image {
695 pub(crate) fn imports(&self) -> Result<Vec<String>> {
696 let imports = self.array(self.field(self.root, 0)?)?;
697 imports
698 .into_iter()
699 .map(|i| self.str_name(self.field(i, 0)?))
700 .collect()
701 }
702
703 pub(crate) fn str_name(&self, mut o: u64) -> Result<String> {
704 let mut parts = Vec::new();
705 while !is_scalar(o) && self.tag(o)? != 0 {
706 parts.push(if self.tag(o)? == 1 {
707 self.str(self.field(o, 1)?)?.to_owned()
708 } else {
709 self.nat_decimal(self.field(o, 1)?)?
710 });
711 o = self.field(o, 0)?;
712 }
713 parts.reverse();
714 Ok(parts.join("."))
715 }
716}
717
718struct Decoder<'a> {
721 img: &'a Image,
722 tables: &'a Tables,
723 rank: u32,
725 cursor: &'a mut Option<usize>,
727 module: Module,
728 memo: Vec<u32>,
731}
732
733const PENDING: u32 = u32::MAX;
735
736impl Decoder<'_> {
737 fn run(&mut self) -> Result<()> {
738 let img = self.img;
739 for c in img.array(img.field(img.root, 2)?)? {
740 self.constant(c)?;
741 }
742 Ok(())
743 }
744
745 fn seen<T>(&self, o: u64) -> Result<(usize, Option<Id<T>>)> {
747 let slot = self.img.slot(o)?;
748 Ok((slot, self.memo[slot].checked_sub(1).map(Id::new)))
749 }
750
751 fn remember<T>(&mut self, slot: usize, id: Id<T>) -> Id<T> {
752 self.memo[slot] = id.0 + 1;
753 id
754 }
755
756 fn name(&mut self, o: u64) -> Result<NameId> {
757 let img = self.img;
758 if is_scalar(o) || img.tag(o)? == 0 {
759 return Ok(ANON);
760 }
761 let (slot, seen) = self.seen(o)?;
762 if let Some(id) = seen {
763 return Ok(id);
764 }
765 let pre = self.name(img.field(o, 0)?)?;
766 let arg = img.field(o, 1)?;
767 let n = match img.tag(o)? {
768 1 => Name::Str(pre, img.str(arg)?.into()),
769 _ => Name::Num(pre, small_nat(arg)?),
770 };
771 let id = self.tables.names.intern(n);
772 Ok(self.remember(slot, id))
773 }
774
775 fn names(&mut self, o: u64) -> Result<Vec<NameId>> {
776 self.img
777 .list(o)?
778 .into_iter()
779 .map(|n| self.name(n))
780 .collect()
781 }
782
783 fn level(&mut self, o: u64) -> Result<LevelId> {
784 let img = self.img;
785 if is_scalar(o) || img.tag(o)? == 0 {
786 return Ok(ZERO);
787 }
788 let (slot, seen) = self.seen(o)?;
789 if let Some(id) = seen {
790 return Ok(id);
791 }
792 let f = |i| img.field(o, i);
793 let l = match img.tag(o)? {
794 1 => Level::Succ(self.level(f(0)?)?),
795 2 => Level::Max(self.level(f(0)?)?, self.level(f(1)?)?),
796 3 => Level::IMax(self.level(f(0)?)?, self.level(f(1)?)?),
797 4 => Level::Param(self.name(f(0)?)?),
798 t => return Err(corrupt(format!("unexpected level tag {t}"))),
799 };
800 let id = self.tables.levels.intern(l);
801 Ok(self.remember(slot, id))
802 }
803
804 fn expr(&mut self, root: u64) -> Result<ExprId> {
807 let img = self.img;
808 let mut work = vec![(root, false)];
809 while let Some((o, ready)) = work.pop() {
810 let slot = img.slot(o)?;
811 let f = |i| img.field(o, i);
812 let tag = img.tag(o)?;
813 if !ready {
814 match self.memo[slot] {
815 0 => {}
816 PENDING => return Err(corrupt("cyclic expression")),
817 _ => continue,
818 }
819 self.memo[slot] = PENDING;
820 work.push((o, true));
821 let subs: &[u64] = match tag {
822 5 => &[0, 1],
823 6 | 7 => &[1, 2],
824 8 => &[1, 2, 3],
825 10 => &[1],
826 11 => &[2],
827 _ => &[],
828 };
829 for &i in subs.iter().rev() {
830 work.push((f(i)?, false));
831 }
832 continue;
833 }
834 let binder = || {
835 Ok::<_, Error>(match img.scalar_u8(o, 8)? {
836 0 => Binder::Default,
837 1 => Binder::Implicit,
838 2 => Binder::StrictImplicit,
839 _ => Binder::InstImplicit,
840 })
841 };
842 let e = match tag {
843 0 => Expr::BVar(small_nat(f(0)?)?),
844 3 => Expr::Sort(self.level(f(0)?)?),
845 4 => {
846 let us = img.list(f(1)?)?;
847 let us = us
848 .into_iter()
849 .map(|l| self.level(l))
850 .collect::<Result<_>>()?;
851 Expr::Const(self.name(f(0)?)?, us)
852 }
853 5 => Expr::App(self.done(f(0)?)?, self.done(f(1)?)?),
854 6 => Expr::Lam(
855 self.name(f(0)?)?,
856 self.done(f(1)?)?,
857 self.done(f(2)?)?,
858 binder()?,
859 ),
860 7 => Expr::Pi(
861 self.name(f(0)?)?,
862 self.done(f(1)?)?,
863 self.done(f(2)?)?,
864 binder()?,
865 ),
866 8 => Expr::Let(
867 self.name(f(0)?)?,
868 self.done(f(1)?)?,
869 self.done(f(2)?)?,
870 self.done(f(3)?)?,
871 ),
872 9 => {
873 let lit = f(0)?;
874 let val = img.field(lit, 0)?;
875 if img.tag(lit)? == 0 {
876 Expr::Nat(img.nat_decimal(val)?.into())
877 } else {
878 Expr::Str(img.str(val)?.into())
879 }
880 }
881 10 => {
882 let id = self.done(f(1)?)?;
883 self.remember(slot, id);
884 continue;
885 }
886 11 => Expr::Proj(self.name(f(0)?)?, small_nat(f(1)?)?, self.done(f(2)?)?),
887 t => {
888 return Err(corrupt(format!(
889 "unexpected expression tag {t} (free or meta variable in a declaration)"
890 )))
891 }
892 };
893 let id = self.tables.exprs.intern(e, self.rank, self.cursor);
894 self.remember(slot, id);
895 }
896 self.done(root)
897 }
898
899 fn done(&self, o: u64) -> Result<ExprId> {
901 self.seen(o)?
902 .1
903 .ok_or_else(|| corrupt("subterm decoded out of order"))
904 }
905
906 fn constant(&mut self, info: u64) -> Result<()> {
907 let img = self.img;
908 let tag = img.tag(info)?;
909 let val = img.field(info, 0)?;
910 let unsafe_flag = match tag {
911 1 => img.scalar_u8(val, 0)? != 1,
912 0 | 3 | 6 => img.scalar_u8(val, 0)? != 0,
913 5 | 7 => img.scalar_u8(val, 1)? != 0,
914 _ => false,
915 };
916 if unsafe_flag {
917 self.module.skipped += 1;
918 return Ok(());
919 }
920 let f = |i| img.field(val, i);
921 let nat = |i| small_nat(f(i)?);
922 let cv = f(0)?;
923 let name = self.name(img.field(cv, 0)?)?;
924 let level_params = self.names(img.field(cv, 1)?)?;
925 for &p in &level_params {
926 self.tables.levels.intern(Level::Param(p));
927 }
928 let ty = self.expr(img.field(cv, 2)?)?;
929 let kind = match tag {
930 0 => Kind::Axiom,
931 1 => {
932 let h = f(2)?;
933 let hints = if !is_scalar(h) {
934 Hints::Regular(img.scalar_u32(h)?)
935 } else if h >> 1 == 0 {
936 Hints::Opaque
937 } else {
938 Hints::Abbrev
939 };
940 Kind::Defn(Defn {
941 value: self.expr(f(1)?)?,
942 hints,
943 all: self.names(f(3)?)?,
944 })
945 }
946 2 => Kind::Thm(Body {
947 value: self.expr(f(1)?)?,
948 all: self.names(f(2)?)?,
949 }),
950 3 => Kind::Opaque(Body {
951 value: self.expr(f(1)?)?,
952 all: self.names(f(2)?)?,
953 }),
954 4 => Kind::Quot(match img.scalar_u8(val, 0)? {
955 0 => QuotKind::Type,
956 1 => QuotKind::Ctor,
957 2 => QuotKind::Lift,
958 _ => QuotKind::Ind,
959 }),
960 5 => Kind::Induct(Inductive {
961 num_params: nat(1)?,
962 num_indices: nat(2)?,
963 all: self.names(f(3)?)?,
964 ctors: self.names(f(4)?)?,
965 num_nested: nat(5)?,
966 is_rec: img.scalar_u8(val, 0)? != 0,
967 is_reflexive: img.scalar_u8(val, 2)? != 0,
968 }),
969 6 => Kind::Ctor(Ctor {
970 induct: self.name(f(1)?)?,
971 cidx: nat(2)?,
972 num_params: nat(3)?,
973 num_fields: nat(4)?,
974 }),
975 7 => {
976 let all = self.names(f(1)?)?;
977 for &ind in &all {
978 self.module.recursors.entry(ind).or_default().push(name);
979 }
980 let mut rules = Vec::new();
981 for r in img.list(f(6)?)? {
982 rules.push(Rule {
983 ctor: self.name(img.field(r, 0)?)?,
984 nfields: small_nat(img.field(r, 1)?)?,
985 rhs: self.expr(img.field(r, 2)?)?,
986 });
987 }
988 Kind::Rec(Rec {
989 all,
990 num_params: nat(2)?,
991 num_indices: nat(3)?,
992 num_motives: nat(4)?,
993 num_minors: nat(5)?,
994 rules,
995 k: img.scalar_u8(val, 0)? != 0,
996 })
997 }
998 t => return Err(corrupt(format!("unexpected constant tag {t}"))),
999 };
1000 self.module.consts.push(Const {
1001 name,
1002 level_params,
1003 ty,
1004 kind,
1005 });
1006 Ok(())
1007 }
1008}
1009
1010#[must_use]
1011pub fn search_path() -> Vec<PathBuf> {
1012 let mut dirs: Vec<PathBuf> = std::env::var_os("LEAN_PATH")
1013 .map(|p| std::env::split_paths(&p).collect())
1014 .unwrap_or_default();
1015 if let Some(root) = std::env::var_os("LEAN_SYSROOT") {
1016 dirs.push(Path::new(&root).join("lib").join("lean"));
1017 }
1018 dirs
1019}