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#[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 #[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#[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#[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#[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
264const 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#[derive(Debug)]
276struct Shared<T>(Vec<Mutex<Shard<T>>>);
277
278impl<T: Hash + Eq> Shared<T> {
279 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#[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 #[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 #[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
371struct 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 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 #[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 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#[derive(Debug)]
493pub struct Exprs(Vec<Vec<Expr>>);
494
495impl Exprs {
496 #[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 #[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
522struct Tables {
524 names: Shared<Name>,
525 levels: Shared<Level>,
526 exprs: SharedExprs,
527}
528
529struct Module {
531 consts: Vec<Const>,
532 recursors: FxHashMap<NameId, Vec<NameId>>,
533 skipped: usize,
534 header: Header,
535}
536
537type 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#[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#[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#[derive(Debug, Default)]
574pub struct Reload {
575 pub modules: Vec<String>,
577 pub consts: Vec<NameId>,
579 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#[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 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 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 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 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 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 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 pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
816 self.order.iter().copied().filter(|&c| !self.is_internal(c))
817 }
818
819 #[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
870fn 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
907fn 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
928pub 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
963struct Decoder<'a> {
966 img: &'a Image,
967 tables: &'a Tables,
968 rank: u32,
970 cursor: &'a mut Option<usize>,
972 module: Module,
973 memo: Vec<u32>,
976}
977
978const 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 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 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 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}