1mod decode;
2mod reload;
3mod table;
4mod term;
5mod walk;
6
7pub use reload::Reload;
8pub use table::{Exprs, Table};
9pub use term::{
10 Binder, Body, Const, Ctor, Defn, Expr, ExprId, Hints, Id, Inductive, Kind, LetNode, Level,
11 LevelId, Name, NameId, QuotKind, Rec, Rule, Theorem, Univs, UnivsId, ANON, ZERO,
12};
13pub(crate) use walk::{Builtins, Dep, Depth, Family};
14
15use self::{
16 decode::{decode_all, Module},
17 reload::{stamp, Live, Loaded, Stamp},
18 table::{Shared, SharedExprs, Tables},
19};
20use crate::{
21 error::{at, Error, Result},
22 inspect::Import,
23 olean::{Header, Image},
24};
25use rustc_hash::{FxHashMap, FxHashSet};
26use std::{
27 borrow::Cow,
28 env,
29 path::{Path, PathBuf},
30 sync::atomic::{AtomicU64, Ordering::Relaxed},
31 thread,
32};
33
34static LINEAGE: AtomicU64 = AtomicU64::new(0);
35
36#[derive(Debug)]
38pub struct Env {
39 pub names: Table<Name>,
40 pub levels: Table<Level>,
41 pub univs: Table<Univs>,
42 pub exprs: Exprs,
43 pub consts: FxHashMap<NameId, Const>,
44 pub order: Vec<NameId>,
45 pub recursors: FxHashMap<NameId, Vec<NameId>>,
46 pub modules: Vec<String>,
47 pub imports: Vec<Vec<Import>>,
49 pub exported: Vec<Option<FxHashMap<NameId, bool>>>,
51 pub header: Header,
52 pub skipped: usize,
53 ends: Vec<usize>,
55 pub(crate) lineage: u64,
56 live: Option<Box<Live>>,
57}
58
59#[rustfmt::skip]
62const KEYWORDS: &[&str] = &[
63 "Prop", "Sort", "Type", "abbrev", "at", "attribute", "axiom", "by", "calc", "class", "def",
64 "deriving", "do", "else", "end", "example", "export", "forall", "from", "fun", "have", "if",
65 "import", "in", "inductive", "instance", "let", "local", "macro", "match", "mutual",
66 "namespace", "noncomputable", "nofun", "nomatch", "opaque", "open", "partial", "private",
67 "protected", "scoped", "section", "set_option", "show", "sorry", "structure", "suffices",
68 "syntax", "then", "theorem", "this", "universe", "unsafe", "variable", "where", "with",
69];
70pub(crate) fn escape(s: &str) -> Cow<'_, str> {
74 let letter = |c: char| {
75 let u = u32::from(c);
76 c.is_ascii_alphabetic()
77 || c == '_'
78 || ((0x3b1..=0x3c9).contains(&u) && u != 0x3bb)
79 || ((0x391..=0x3a9).contains(&u) && u != 0x3a0 && u != 0x3a3)
80 || matches!(u, 0x3ca..=0x3fb | 0x1f00..=0x1ffe | 0x2100..=0x214f | 0x1d49c..=0x1d59f)
81 };
82 let rest = |c: char| {
83 letter(c)
84 || c.is_ascii_digit()
85 || matches!(c, '\'' | '!' | '?')
86 || matches!(u32::from(c), 0x2080..=0x2089 | 0x2090..=0x209c | 0x1d62..=0x1d6a | 0x2c7c)
87 };
88 let mut cs = s.chars();
89 let plain = cs.next().is_some_and(letter) && cs.all(rest) && !KEYWORDS.contains(&s);
90 if plain {
91 Cow::Borrowed(s)
92 } else if s.contains(['»', '\\']) {
93 Cow::Owned(format!("«{}»", s.replace('\\', "\\\\").replace('»', "\\»")))
94 } else {
95 Cow::Owned(format!("«{s}»"))
96 }
97}
98
99fn discover_all(search: &[PathBuf], roots: &[&str]) -> Result<Vec<(String, PathBuf)>> {
100 let mut seen = FxHashSet::default();
101 let mut found = Vec::new();
102 for root in roots {
103 discover(search, root, &mut seen, &mut found)?;
104 }
105 Ok(found)
106}
107
108fn discover(
110 search: &[PathBuf],
111 module: &str,
112 seen: &mut FxHashSet<String>,
113 out: &mut Vec<(String, PathBuf)>,
114) -> Result<()> {
115 if !seen.insert(module.to_owned()) {
116 return Ok(());
117 }
118 let path = resolve(search, module)?;
119 let img = Image::open(&path)?;
120 let imports = img.imports().map_err(at(&path))?;
121 drop(img);
122 for import in &imports {
123 discover(search, &import.module, seen, out)?;
124 }
125 out.push((module.to_owned(), path));
126 Ok(())
127}
128
129pub fn resolve(search: &[PathBuf], module: &str) -> Result<PathBuf> {
132 let rel: PathBuf = module.split('.').collect();
133 search
134 .iter()
135 .map(|dir| dir.join(&rel).with_extension("olean"))
136 .find(|p| p.is_file())
137 .ok_or_else(|| Error::ModuleNotFound(module.to_owned()))
138}
139
140#[must_use]
141pub fn search_path() -> Vec<PathBuf> {
142 let mut dirs: Vec<PathBuf> =
143 env::var_os("LEAN_PATH").map_or_default(|p| env::split_paths(&p).collect());
144 if let Some(root) = env::var_os("LEAN_SYSROOT") {
145 dirs.push(Path::new(&root).join("lib").join("lean"));
146 }
147 dirs
148}
149
150impl Env {
151 pub fn load(search: &[PathBuf], roots: &[&str]) -> Result<Self> {
153 let jobs = thread::available_parallelism().map_or(1, usize::from);
154 Self::load_with(search, roots, jobs, &|_, _| {})
155 }
156
157 pub fn load_with(
163 search: &[PathBuf],
164 roots: &[&str],
165 jobs: usize,
166 progress: &(dyn Fn(usize, usize) + Sync),
167 ) -> Result<Self> {
168 Self::build(search, roots, jobs, progress, false, false)
169 }
170
171 fn build(
172 search: &[PathBuf],
173 roots: &[&str],
174 jobs: usize,
175 progress: &(dyn Fn(usize, usize) + Sync),
176 live: bool,
177 lazy: bool,
178 ) -> Result<Self> {
179 let found = discover_all(search, roots)?;
180 let stamps: Vec<Stamp> = found.iter().map(|(_, p)| stamp(p)).collect();
181 let bytes: u64 = stamps.iter().flatten().map(|(len, _)| len).sum();
184 let estimate = |per: u64| usize::try_from(bytes / per).unwrap_or(0);
185 let tables = Tables {
186 names: Shared::new(Name::Anon, estimate(1200)),
187 levels: Shared::new(Level::Zero, 0),
188 univs: Shared::new(Univs(Box::new([])), 0),
189 exprs: SharedExprs::new(estimate(64)),
190 };
191 let paths: Vec<_> = found.iter().map(|(_, p)| p.as_path()).enumerate().collect();
192 let decoded = decode_all(&tables, &paths, jobs, progress, lazy);
193 let (exprs, index, ranks) = tables.exprs.freeze();
194 let kept = live.then_some((index, ranks));
195 let decoded = decoded?;
196 let mut env = Self {
197 names: tables.names.freeze(),
198 levels: tables.levels.freeze(),
199 univs: tables.univs.freeze(),
200 exprs,
201 consts: FxHashMap::default(),
202 order: Vec::new(),
203 recursors: FxHashMap::default(),
204 modules: Vec::new(),
205 imports: Vec::new(),
206 exported: Vec::new(),
207 header: Header::default(),
208 skipped: 0,
209 ends: Vec::new(),
210 lineage: LINEAGE.fetch_add(1, Relaxed),
211 live: None,
212 };
213 let loaded: Vec<_> = found
214 .into_iter()
215 .zip(stamps)
216 .zip(decoded)
217 .map(|(((module, path), stamp), m)| env.add(module, path, stamp, m))
218 .collect();
219 env.index(&loaded);
220 if let Some((index, ranks)) = kept {
221 env.live = Some(Box::new(Live {
222 search: search.to_vec(),
223 roots: roots.iter().map(|&r| r.to_owned()).collect(),
224 jobs,
225 index,
226 ranks,
227 loaded,
228 }));
229 }
230 Ok(env)
231 }
232
233 fn add(&mut self, module: String, path: PathBuf, stamp: Stamp, m: Module) -> Loaded {
234 let consts = m.consts.iter().map(|c| c.name).collect();
235 self.consts
236 .extend(m.consts.into_iter().map(|c| (c.name, c)));
237 Loaded {
238 module,
239 path,
240 stamp,
241 consts,
242 recursors: m.recursors,
243 skipped: m.skipped,
244 header: m.header,
245 imports: m.imports,
246 exported: m.exported,
247 pending: m.pending,
248 }
249 }
250
251 fn index(&mut self, loaded: &[Loaded]) {
253 self.order = loaded
254 .iter()
255 .flat_map(|l| l.consts.iter().copied())
256 .collect();
257 self.recursors.clear();
258 for (ind, recs) in loaded.iter().flat_map(|l| &l.recursors) {
260 let all = self.recursors.entry(*ind).or_default();
261 for r in recs {
262 if !all.contains(r) {
263 all.push(*r);
264 }
265 }
266 }
267 self.modules = loaded.iter().map(|l| l.module.clone()).collect();
268 self.imports = loaded.iter().map(|l| l.imports.clone()).collect();
269 self.exported = loaded.iter().map(|l| l.exported.clone()).collect();
270 self.header = loaded.last().map_or_default(|l| l.header.clone());
271 self.skipped = loaded.iter().map(|l| l.skipped).sum();
272 self.ends = loaded
273 .iter()
274 .scan(0, |end, l| {
275 *end += l.consts.len();
276 Some(*end)
277 })
278 .collect();
279 }
280
281 #[must_use]
283 pub fn module_consts(&self, m: usize) -> &[NameId] {
284 let start = m.checked_sub(1).map_or(0, |p| self.ends[p]);
285 &self.order[start..self.ends[m]]
286 }
287
288 pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
290 self.order.iter().copied().filter(|&c| !self.is_internal(c))
291 }
292
293 #[must_use]
296 pub fn find_name(&self, dotted: &str) -> Option<NameId> {
297 let (mut pre, mut rest) = (ANON, dotted);
298 loop {
299 let (n, tail) = if let Some(r) = rest.strip_prefix('«') {
300 let (mut s, mut cs) = (String::new(), r.char_indices());
301 let end = loop {
302 match cs.next()? {
303 (_, '\\') => s.push(cs.next()?.1),
304 (i, '»') => break i + '»'.len_utf8(),
305 (_, c) => s.push(c),
306 }
307 };
308 (Name::Str(pre, s.into()), &r[end..])
309 } else {
310 let (s, tail) = rest.split_at(rest.find('.').unwrap_or(rest.len()));
311 let n = s
312 .parse()
313 .map_or_else(|_| Name::Str(pre, s.into()), |i| Name::Num(pre, i));
314 (n, tail)
315 };
316 pre = self.names.get(&n)?;
317 match tail.strip_prefix('.') {
318 Some(t) => rest = t,
319 None => return tail.is_empty().then_some(pre),
320 }
321 }
322 }
323
324 #[must_use]
327 pub fn display(&self, n: NameId) -> String {
328 self.join(n, true)
329 }
330
331 pub(crate) fn dotted(&self, n: NameId) -> String {
333 self.join(n, false)
334 }
335
336 fn join(&self, n: NameId, escaped: bool) -> String {
337 let (pre, last) = match &self.names[n] {
338 Name::Anon => return String::new(),
339 Name::Str(p, s) if escaped => (*p, escape(s).into_owned()),
340 Name::Str(p, s) => (*p, s.to_string()),
341 Name::Num(p, i) => (*p, i.to_string()),
342 };
343 match pre {
344 ANON => last,
345 p => format!("{}.{last}", self.join(p, escaped)),
346 }
347 }
348
349 #[must_use]
350 pub fn is_internal(&self, n: NameId) -> bool {
351 match &self.names[n] {
352 Name::Anon => false,
353 Name::Str(p, s) => s.starts_with('_') || self.is_internal(*p),
354 Name::Num(p, _) => self.is_internal(*p),
355 }
356 }
357}