Skip to main content

olean_export/env/
mod.rs

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/// Every constant reachable from a set of root modules, in import order.
37#[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    /// The direct imports of each module in `modules`.
48    pub imports: Vec<Vec<Import>>,
49    /// What each module in the module system exports, true where only the statement.
50    pub exported: Vec<Option<FxHashMap<NameId, bool>>>,
51    pub header: Header,
52    pub skipped: usize,
53    /// Where each module's constants end in `order`.
54    ends: Vec<usize>,
55    pub(crate) lineage: u64,
56    live: Option<Box<Live>>,
57}
58
59/// Identifier-shaped tokens of Lean's term and command syntax, which a name must not print
60/// as. Universe syntax adds `max` and `imax`, which the statement printer escapes itself.
61#[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];
70/// A name component in `«»` unless Lean would read it back as itself unescaped. Lean has no
71/// way to write a `»` in a name, so `»` and `\` are written after a `\`, which no name Lean
72/// can print contains.
73pub(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
108/// Find `module` and its imports, appending them to `out` in import order.
109fn 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
129/// The `.olean` for a dotted module name such as `Init.Prelude`, from the first directory
130/// of `search` that has it.
131pub 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    /// Load `roots` and their transitive imports, resolving modules against `search`.
152    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    /// Like [`Env::load`] on `jobs` threads, calling `progress` with the number of modules
158    /// and constants decoded so far.
159    ///
160    /// Modules decode in parallel straight into shared tables, and the result is the same
161    /// for any `jobs`.
162    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        // Sizing the tables up front avoids rehashing them while they grow. Across Lean and
182        // Mathlib there is about one expression per 64 bytes of olean and one name per 1200.
183        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    /// Rebuild the load order and everything summed over modules.
252    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        // two modules may both declare a type, as realized or independent copies
259        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    /// The constants module `m` declares, in load order.
282    #[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    /// The constants `lean4export` exports when given no explicit names.
289    pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
290        self.order.iter().copied().filter(|&c| !self.is_internal(c))
291    }
292
293    /// Look up a name such as `Nat.add` or `Foo.«bar.baz»`, as [`Env::display`] writes it,
294    /// without interning it.
295    #[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    /// `n` as Lean reads it back: components that are not plain identifiers, or are
325    /// keywords, go in `«»`.
326    #[must_use]
327    pub fn display(&self, n: NameId) -> String {
328        self.join(n, true)
329    }
330
331    /// `n` with its components joined as they are, as `declRangeExt` keys it.
332    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}